@Mihai Visuian. O sa incerc eu sa-ti explic.
Cine vrea sa se mai gandeasca, il sfatuiesc sa sara peste postul asta.
Incep cu un caz mai special: intervalul [1, 10^B - 1]. Te intereseaza toate numerele diferite x care se pot scrie ca produs de cel mult B cifre. Fiecare numar x va avea o descompunere in factori primi. Asadar, te intereseaza toate descompunerile in factori primi diferite. Observi ca singurii factori primi care pot aparea in descompuneri sunt 2, 3, 5 si 7. Cea mai mare descompunere ipotetica ar fi 2^60 * 3^40 * 5 ^ 20 * 7 ^ 20 (daca ai folosi de B ori cifrele 8, 9, 5 si 7). Deci sunt maxim 60 * 40 * 20^2 posibilitati = 960000 de descompuneri, care pot fi iterate. Mai ramane de rezolvat o problema: avand o descompunere 2^a * 3^b * 5^c * 7^d, se poate obtine ca produs de cel mult B cifre? Pentru factorii 5 si 7, trebuie folosite c + d cifre (c cifre de 5 si d cifre de 7). Acum, pentru puterile lui 2, este optim ca folosind o singura cifra de 8 sa reduc a-ul cu 3. Dupa ce nu se mai poate scadea 3 din a (a < 3), am 3 posibilitati:
1. folosesc o cifra de 6 si obtin un a si un b mai putin in descompunere
2. folosesc o cifra de 4 si obtin si obtin 2 de a mai putin in descompunere
3. folosesc o cifra de 2 si obtin un a mai putin de descompunere
Aceeasi situatie se intampla si pentru 3. Folosind greedy, este optim sa iau cat mai mult posibil. Intai o sa aplic 2. pe numerele a si b. Daca atat a cat si b ajung 1, le aplic 1. (folosind o cifra de 6, in loc de una de 2 si una de 3) Altfel, folosind o 3. o sa iau cifra. Acum am numarul de cifre minim (adunand toate numerele de mai sus) pentru care se poate obtine descompunerea 2^a * 3^b * 5^c * 7^d. Daca este <= B, atunci descompunerea e valida.
Mai ramane problema pe caz general [10^A, 10^B - 1]. Aceasta poate fi redusa usor la problema de mai sus. Daca pt o descompunere, numarul minim de cifre este < A, se mai pot adauga 1 care nu vor influenta rezultatul pana se vor obtine A cifre.
Descompunerile in factori primi ajuta pentru numere >= 2, dar mai raman numerele 0 si 1. Numarul 0 se poate obtine de fiecare data cand B > 1 (spre exemplu, numarul 10 va genera valoarea 0). Numarul 1 se poate obtine pt orice valoare a lui A, deci la rezultat se va adauga 1 si se va obtine rezultatul final. Observi ca valoarea lui A nu influenteaza deloc problema.
Sper ca ti-am fost de ajutor. Mult succes. Mi-au placut problemele, mai ales ca au necesitat gandire, nu numai algoritmi. As vrea si eu un hint la Triangles.
Am gasit o solutie O(N * logN), care nu intra in timp.
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena