h3(#problema-2). Problema 2: 'Ugly numbers':http://code.google.com/codejam/contest/dashboard?c=32015#s=p1&a=1 (Google Code Jam 2008, Round 1C)

bq. Un număr se numeşte *urât* dacă este divizibil prin oricare dintre numerele prime de o singură cifră, mai exact 2, 3, 5, 7. Se dă un şir de N cifre. Între fiecare 2 cifre consecutive se poate insera unul dintre semnele + sau -. Dacă nu se inserează un semn, cele 2 cifre sunt concatentate astfel încât să se obţină un număr. Pentru un şir dat de cifre si o variantă de a adăuga semne, prin evaluarea expresiei matematice obţinute prin inserarea semnelor se obţine un număr, numit numărul generat. Să se calculeze câte dintre cele 3^N-1^ variante de a insera semnele generează numere urâte.

bq. Un număr se numeşte *urât* dacă este divizibil prin oricare dintre numerele prime de o singură cifră, mai exact $2, 3, 5, 7$. Se dă un şir de $N$ cifre. Între fiecare 2 cifre consecutive se poate insera unul dintre semnele + sau -. Dacă nu se inserează un semn, cele 2 cifre sunt concatentate astfel încât să se obţină un număr. Pentru un şir dat de cifre si o variantă de a adăuga semne, prin evaluarea expresiei matematice obţinute prin inserarea semnelor se obţine un număr, numit numărul generat. Să se calculeze câte dintre cele $3^N-1^$ variante de a insera semnele generează numere urâte.

h3. Exemplu:

Pentru cifrele *123456*, expresia *1+234-5+6 = 236* care este număr urât, iar *123+4-56 = 71* nu este număr urât.

Pentru cifrele $123456$, expresia $1+234-5+6 = 236$ care este număr urât, iar $123+4-56 = 71$ nu este număr urât.

h3. Rezolvare:

Observăm că un număr este urât dacă dă cel puţin o dată restul 0 la împărţirea la numerele 2, 3, 5, 7. O abordare a problemei este parcurgerea tuturor variantelor de inserare şi calcularea celor 4 resturi, verificând dacă cel puţin unul este 0.
Vom folosi aritmetica modulară pentru a obţine o soluţie mai eficientă a problemei. Vom împărţi cele 3^N-1^ variante în clase, fiecare clasă reprezentând toate numerele care dau resturile $(r{~2~}, r{~3~}, r{~5~}, r{~7~})$ la împărţirea la cele 4 numere. Calculând pentru fiecare clasă numărul de numere generate, rezultatul final va fi suma valorilor calculate pentru toate clasele pentru care cel puţin un rest este egal cu 0. Intuim că putem utiliza clasele de resturi într-o soluţie cu programare dinamică.
Vom utiliza şirul auxiliar $V[i][j]$ reprezentând numărul format prin concatenarea cifrelor de pe poziţiile consecutive $i, i+1, ..., j$ din şirul dat, fără inserarea unor semne între cifre. De exemplu, @V[2][4] = 234@. Dacă notăm cu $C[i][r{~2~}][r{~3~}][r{~5~}][r{~7~}]$ numărul de variante formate cu primele *i* cifre pentru care clasa de resturi este $(r{~2~}, r{~3~}, r{~5~}, r{~7~})$. Observăm că orice astfel de variantă se obţine dintr-o variantă cu $j < i$ cifre după care adăugam + sau - apoi concatenăm restul cifrelor până la *i* fără semne. Dacă resturile pentru varianta cu *j* cifre erau $(r{~2~}, r{~3~}, r{~5~}, r{~7~})$ atunci resturile pentru varianta nouă $(r'{~2~}, r'{~3~}, r'{~5~}, r'{~7~})$ sunt:

Observăm că un număr este urât dacă dă cel puţin o dată restul 0 la împărţirea la numerele $2, 3, 5, 7$. O abordare a problemei este parcurgerea tuturor variantelor de inserare şi calcularea celor 4 resturi, verificând dacă cel puţin unul este 0.
Vom folosi aritmetica modulară pentru a obţine o soluţie mai eficientă a problemei. Vom împărţi cele $3^N-1^$ variante în clase, fiecare clasă reprezentând toate numerele care dau resturile $(r{~2~}, r{~3~}, r{~5~}, r{~7~})$ la împărţirea la cele 4 numere. Calculând pentru fiecare clasă numărul de numere generate, rezultatul final va fi suma valorilor calculate pentru toate clasele pentru care cel puţin un rest este egal cu 0. Intuim că putem utiliza clasele de resturi într-o soluţie cu programare dinamică.
Vom utiliza şirul auxiliar $V[i][j]$ reprezentând numărul format prin concatenarea cifrelor de pe poziţiile consecutive $i, i+1, ..., j$ din şirul dat, fără inserarea unor semne între cifre. De exemplu, @V[2][4] = 234@. Dacă notăm cu $C[i][r{~2~}][r{~3~}][r{~5~}][r{~7~}]$ numărul de variante formate cu primele $i$ cifre pentru care clasa de resturi este $(r{~2~}, r{~3~}, r{~5~}, r{~7~})$. Observăm că orice astfel de variantă se obţine dintr-o variantă cu $j < i$ cifre după care adăugam + sau - apoi concatenăm restul cifrelor până la $i$ fără semne. Dacă resturile pentru varianta cu $j$ cifre erau $(r{~2~}, r{~3~}, r{~5~}, r{~7~})$ atunci resturile pentru varianta nouă $(r'{~2~}, r'{~3~}, r'{~5~}, r'{~7~})$ sunt:

<tex> $r_2' = (r_2 +/- V[j+1][i])\% 2$</tex>
<tex> $r_3' = (r_3 +/- V[j+1][i])\% 3$</tex>
<tex> $r_5' = (r_5 +/- V[j+1][i])\% 5$</tex>
<tex> $r_7' = (r_7 +/- V[j+1][i])\% 7$</tex>

Atunci numărul total de variante cu *i* cifre este suma după toate valorile *j* ale numerelor de variante cu *j* cifre:

Atunci numărul total de variante cu $i$ cifre este suma după toate valorile $j$ ale numerelor de variante cu $j$ cifre:

<tex> $C[i][r_2'][r_3'][r_5'][r_7'] = \sum_{j<i} C[j][r_2][r_3][r_5][r_7]$ </tex>
== code(cpp)    |