infoarena

Aici puteţi discuta despre problema Peluza Nord (http://infoarena.ro/problema/peluzanord).

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.

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.

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

Ai o idee exact mai sus  :)

Edit: se pare ca se incadreaza in timp cu memoizare  =D&gt;