h1(#anagrame2). 'Solutia':algoritmiada-2019/runda-finala/solutii/anagrame2 problemei 'Anagrame2':problema/anagrame2

h1(#anagrame2). 'Solutia':algoritmiada-2019/runda-finala/solutii/anagrame2 problemei 'Anagrame2':problema/anagrame2
 
Multumim lui ==user(user="FunnyStocky" type="tiny")== pentru editorial!
 
* _+Voi utiliza si cod in **limbajul c++** pentru a usura intelegere solutiei+_
 
 
|_. Capitol 1 : |_. interactiunea|
 
 
**Cum realizam interactiunea?**
Vom scrie o functie "ask" care ne va usura procesul de **interactiune** :
 
== code(cpp) |
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)
 
|_. Capitol 2 : |_. transformare din numar in caracter|
 
Vom scrie o functie "getch" care ne va ajuta sa transformam un numar intr-un caracter
 
== code(cpp) |
char getch(int i) {
    if (i <= 9)
        return (char) (i + '0');
    else
        return (char) (i - 10 + 'a');
}
==
 
|_. Capitol 3 : |_. Caz particular in care numarul este **0**|
 
daca nu avem alte cifre in afara de **0** => **numarul nostru** este chiar **0**
 
== code(cpp) |
if (f[0] == len) {
    ask("0");
    continue;
}
==
 
 
|_. Capitol 4 : |_. solutia de 23 de puncte|
 
# Pentru **23 de puncte**, trebuie sa punem mai putin de **900 de intrebari**.
# Notam cu **b = baza numarului**
# Notam cu **len = f [0] + f [1] + ... + f [b - 1]**, **len** este lungimea numarului in baza **b**
# din enunt avem **1 <= len, b <= 30**
# avem **30 * 30 = 900**, de aici ne putem sa ne gandim ca avem nevoie de o solutie care pune **len * b** intrebari
# 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
# presupunem ca stim deja **primele k cifre** ale numarului, ele fiind de forma **X1, X2, ..., XK, ?, ?, ?, ..., ?, ?** (ultimele **len - k** cifre sunt inca necunoscute)
# 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)**
# vrem sa verificam daca **x[K+1] = cif**
# 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
 
== code(cpp) |
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]**
 
== code(cpp) |
 
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
        }
    }
}
 
==
 
|_. Capitol 5 : |_. solutia de 100 de puncte|
 
# se garanteaza ca sunt cel mult **2^58^** numere distincte care se pot forma cu frecventele din input
# de aici, vine si ideea de a folosi **cautarea binara**
# ca sa calculam numarul total de anagrame o sa folosim **formula combinarilor cu repetitii : k = len! / (f [0]! * f [1]! * ... * f[b-1]!)**
# trebuie sa avem grija sa **NU** numaram si "anagramele" care incep cu 0, numarul acestora fiind **zero = k / len * f [0]**
# 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
# astfel fiecarei anagrame i se atribuie o valoare x
# **in exemplu, testul 1** :
## **k = 6 si zero = 2**
## anagrama 1 : **012**
## anagrama 2 : **021**
## anagrama 3 : **102**
## anagrama 4 : **120**
## anagrama 5 : **201**
## anagrama 6 : **210**
# deoarece anagrama secreta **NU poate incepe cu 0** => valoarea anagramei noastre este **[zero + 1, zero + 2, ..., zero + k]**
# acum ne trebuie o functie care construieste a **x-a anagrama** a numarului din input
## vom lua **la rand pozitiile de la 1 la len** si ca la solutia de 23 de puncte o sa construim secvential solutia
## 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
## 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
 
== code(cpp) |
 
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]!)**
 
== code(cpp) |
 
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!!!**
 
== code(cpp) |
 
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;
}
 
==