1445 Peluza Nord

[•wefgef]

Aici puteţi discuta despre problema Peluza Nord.

[•horatiu11]

Buna, imi puteti da si mie o idee cam cum ar trebui rezolvata problema asta?
Am citit acest articol http://en.wikipedia.org/wiki/Harshad_number , insa nu prea pricep ce si cum.

[•florin.elfus]

Nu am rezolvat problema inca, dar cred ca se poate face cu o dinamica. Intai observi ca numarul de numere shukare din intervalul [A, B] este de fapt numarul de numere shukare din intervalul [1, B] - numarul de numere shukare din intervalul [1, A - 1].

Acum pentru a calcula numarul de numere shukare din [1, X] iti tii urmatoarea dinamica:

dp[nr_cifre][suma_cifre_actuala][suma_cifre_dorita][rest_modulo_suma_cifre_dorita][prefix_egal] = numarul de numere <= X astfel incat contin nr_cifre cifre, suma cifrelor celor nr_cifre este suma_cifre_actuala, dupa ce mai adaug alte cifre doresc sa obtin suma_cifre_dorita, restul sumei cifrelor celor nr_cifre de pana acum modulo suma_cifre dorita este rest_modulo_suma_cifre_dorita, iar prefix_egal este 1 daca pana acum toate cele nr_cifre adaugate coincid cu primele nr_cifre ale numarului X si 0 altfel.

Pentru rezultat o sa ai ceva gen suma din dp[orice][orice2][orice2][0][0 sau 1]. La recurente e putin mai complicat Nu am testat-o, dar sper sa fie bine.

[•bciobanu]

Ma poate ajuta cineva cu o idee? Am o solutie in O(3 * 10 * MAX_SUMA_CIFRE ^ 3 * NR_CIFRE).

[•klamathix]

Ai o idee exact mai sus 

[•bciobanu]

Edit: se pare ca se incadreaza in timp cu memoizare