Solutia problemei Anagrame2

Multumim lui Mihnea Andreescu •FunnyStocky pentru editorial!

• Voi utiliza si cod in limbajul c++ pentru a usura intelegere solutiei

Cum realizam interactiunea?
Vom scrie o functie "ask" care ne va usura procesul de interactiune :

string ask(string s) {
    cout << s << endl;
    cin >> s;
    return s;
}

(daca folosim "<< endl", se realizeaza flush automat si nu mai este nevoie sa facem flush manual)

char getch(int i) {
    if (i <= 9)
        return (char) (i + '0');
    else
        return (char) (i - 10 + 'a');
}

daca nu avem alte cifre in afara de 0 => numarul nostru este chiar 0

if (f[0] == len) {
    ask("0");
    continue; 
}

1. Pentru 23 de puncte, trebuie sa punem mai putin de 900 de intrebari.
2. Notam cu b = baza numarului
3. Notam cu len = f [0] + f [1] + ... + f [b - 1], len este lungimea numarului in baza b
4. din enunt avem 1 <= len, b <= 30
5. avem 30 * 30 = 900, de aici ne putem sa ne gandim ca avem nevoie de o solutie care pune len * b intrebari
6. ne gandim sa parcurgem cifrele numarului de la stanga la dreapta (de la cea mai semnificativa la cea mai nesemnificativa) si sa aflam cifrele numarului ascuns in aceasta ordine
7. presupunem ca stim deja primele k cifre ale numarului, ele fiind de forma X1, X2, ..., XK, ?, ?, ?, ..., ?, ? (ultimele len - k cifre sunt inca necunoscute)
8. verificam ce cifra am putea sa punem, pornind de la cea mai mica posibila la cea mai mare (ex: cif = 0, 1, 2, ..., b - 1)
9. vrem sa verificam daca x[K+1] = cif
10. avem Q = x [1], x [2], ..., x[k+1], ?, ?, ?, ..., ? inlocuim cifrele "necunoscute" astfel incat sa formam cel mai mare numar posibil care sa fie anagrama a numarului nostru

string build_max_string(string cur) { // cur = x[1], x[2], ..., x[k+1]
    for (int j = b - 1; j >= 0; j--)
        for (int i = 0; i < f[j]; i++)
            cur += getch(j);
    return cur;
}

11. intrebam ask(numarul Q) si notam O = ask(numarul Q)
12. daca O = "<" => numarul maxim pe care il putem obtine este mai mic decat numarul necunoscut => trecem mai departe si verificam daca x[k+1] poate sa fie cif+1
13. daca O = "=" => numarul Q este numarul necunoscut => trecem imediat la urmatorul test
14. daca O = ">" => numarul maxim pe care il putem obtine este mai mare decat numarul necunoscut => x[k+1] este cif => trecem mai departe sa calculam x[k+2]

bool ok = 0;
string cur;
for (int step = 1; step <= len && !ok; step++) {
    for (int i = (step == 1); i < b; i++) {
        if (f[i] > 0) {
            f[i]--;
            string curi = cur + getch(i), mxposi = build_max_string(curi);
            string s = ask(mxposi);
            if (s == "=") { /// pasul 13
                ok = 1;
                break;
            }
            if (s == ">") { /// pasul 14
                cur = curi;
                break;
            }
            f[i]++; /// pasul 12
        }
    }
}

1. se garanteaza ca sunt cel mult 2⁵⁸ numere distincte care se pot forma cu frecventele din input
2. de aici, vine si ideea de a folosi cautarea binara
3. ca sa calculam numarul total de anagrame o sa folosim formula combinarilor cu repetitii : k = len! / (f [0]! * f [1]! * ... * f[b-1]!)
4. trebuie sa avem grija sa NU numaram si "anagramele" care incep cu 0, numarul acestora fiind zero = k / len * f [0]
5. vom lucra pe numere de tip long long pe indici, atribuind fiecarui numar natural de la 1 la k o anagrama a numarului din input
6. astfel fiecarei anagrame i se atribuie o valoare x
7. in exemplu, testul 1 :
   1. k = 6 si zero = 2
   2. anagrama 1 : 012
   3. anagrama 2 : 021
   4. anagrama 3 : 102
   5. anagrama 4 : 120
   6. anagrama 5 : 201
   7. anagrama 6 : 210
8. deoarece anagrama secreta NU poate incepe cu 0 => valoarea anagramei noastre este [zero + 1, zero + 2, ..., zero + k]
9. acum ne trebuie o functie care construieste a x-a anagrama a numarului din input
   1. vom lua la rand pozitiile de la 1 la len si ca la solutia de 23 de puncte o sa construim secvential solutia
   2. mentinem o variabila aux care ne spune cate anagrame au ca prefix sirul nostru de pana acum, initial aux = k, sirul nostru fiind vid si toate sirurile avand ca prefix sirul vid
   3. presupunem ca am aflat primele k pozitii si vrem sa o aflam pe a k + 1 - a pozitie; parcurgem toate caracterele posibile si vedem daca numarul de anagrame care au prefix-ul mai mic sau egal decat cele k + 1 pozitii depaseste variabila noastra x

string gen(ll x) {
    for (int j = 0; j < n; j++)
        a[j] = f[j];
    string s;
    ll aux = k;
    for (int i = 1; i <= len; i++) {
        ll sum = 0;
        for (int j = 0; j < n; j++) {
            ll t = aux * a[j] / (len - i + 1);
            sum += t;
            if (sum >= x) {
                s += getch(j);
                a[j]--;
                aux = t;
                x -= (sum - t);
                break;
            }
        }
    }
    return s;
}

10. trebuie sa calculam k si zero
11. deoarece 30! este prea mare si nu intra pe long long, dar rezultatul va intra pe long long, vom retine exponentii fiecarui numar prim <= 30; amintim ca : k = len! / (f [0]! * f [1]! * ... * f[b-1]!)

memset(exp, 0, sizeof exp);
for (int i = 2; i <= len; i++) {
    int cop = i;
    for (int j = 2; j <= cop; j++)
        while (cop % j == 0)
            cop /= j, exp[j]++;
}
for (int i = 0; i < n; i++)
    for (int k = 2; k <= f[i]; k++) {
        int cop = k;
        for (int j = 2; j <= cop; j++)
            while (cop % j == 0)
                cop /= j, exp[j]--;
    }
k = 1;
for (int i = 1; i <= len; i++)
    for (int j = 1; j <= exp[i]; j++)
        k *= i;
zero = all * f[0] / len;

12. ultimul pas : cautarea binara
ATENTIE trebuie inceputa de la zero + 1 ca limita inferioara si k ca limita superioara pentru a NU lua in considerare numerele care incep cu 0!!!

ll lo = zero + 1, hi = all;
while (lo <= hi) {
    ll mid = (lo + hi) / 2;
    string ch = ask(gen(mid));
    if (ch == "=")
        break;
    if (ch == "<")
        lo = mid + 1;
    else
        hi = mid - 1;
}