Solutia problemei Voodoo

Pentru început, trebuie să analizăm cum ar arăta funcţia GB(N). O să analizăm cazul B = 10 pentru a ne fi mai uşor de vizualizat, chiar dacă nu o să fie în teste.

  • G10(0) = 1
  • G10(1) = 10
  • G10(2) = 19
  • G10(3) = 199
  • G10(4) = 1999...9 (de 22 de ori)

De la un punct încolo, putem să observăm deja o formă generală: G începe cu 1 şi este urmat de mai mulţi de 9.

Demonstraţie

I) Fie X < Y. Atunci cel mai mic număr cu suma cifrelor X este mai mic decât cel mai mic număr cu suma cifrelor Y.

Putem genera cele mai mici numere folosind o strategie greedy, pentru început minimizăm numărul de cifre. Pentru asta, vom folosi cât mai multe cifre de 9. Numărul de cifre de 9 va fi [X / 9], iar prima cifră va fi x % 9, asta dacă e diferită de 0. Dacă cele două numere au acelaşi număr de cifre, atunci cel cu suma cifrelor X va fi mai mic, deoarece restul lui la împărţirea cu 9 va fi mai mic. Altfel Y va avea mai multe cifre şi va fi mai mare.

II) Restul unui număr X la împărţirea cu 9, va fi egal cu restul sumei cifrelor lui X la împărţirea cu 9. Pentru a generaliza problema, restul unui număr la împărţirea cu B, va fi egal cu restul sumei cifrelor lui X în baza B la împărţirea cu B.

Această afirmaţie poate fi demonstrată prin inducţie. Pentru numerele de la 0 până la B - 2, afirmaţia este evidentă. Dacă adăugăm repetat la aceste numere B - 1, avem următoarele cazuri:

  • Cea mai din dreapta cifră creşte cu B - 1 şi nu avem transport, caz în care suma cifrelor creşte cu B - 1 şi restul se păstrează.
  • Cea mai din dreapta cifră, care la început să zicem că e t, creşte cu B - 1, dar după trebuie să ducem transport la următoarea cifră, altfel ea va deveni t + B - 1 - B = t - 1, deci ea scade cu 1, dar următoarea cifră va creşte cu 1 şi nu va duce transport în continuare. În acest caz suma cifrelor rămâne aceeaşi.
  • Se întâmplă toate lucrurile din cazul anterior, dar a doua cifră va duce transport, deci ea se va transforma în t + 1 - B = t - 1, dar cifra următoare va creşte cu 1 şi nu va duce transport, deci suma cifrelor scade cu B - 1 şi restul se păstrează.
  • ...

III) G10(N) = 199999...9 pentru N ≥ 2, sau, generalizat, GB(N) = 1(B-1)(B-1)(B-1)...(B-1) în baza B.

Folosindu-ne de I) şi II), putem genera într-un mod recursiv pe GB(N), fixându-i suma cifrelor ca fiind GB(N - 1). Putem demonstra într-un mod inductiv faptul că numărul va avea forma de mai sus:

  • GB(2) = 1(B-1) în baza B
  • GB(N) va avea multe cifre de B - 1 la sfârşit, rămâne de demonstrat faptul că prima cifră va fi 1. Aceasta va fi defapt restul sumei cifrelor la (B - 1). Cum GB(N - 1), care este şi suma cifrelor lui GB(N), este format dintr-un singur 1 şi multe cifre de B - 1, atunci, folosind II), restul lui la împărţirea cu B - 1 va fi restul sumei cifrelor sale la împărţirea cu B - 1, deci prima cifră va fi 1.

Soluţie de 20 de puncte

O primă soluţie care ne-ar veni în minte ar fi să implementăm modul de construcţie inductivă de mai sus.

Soluţie de 70 de puncte

Vom analiza în continuare G10(N) şi vom încerca să rescriem funcţia.

  • G10(2) = 19 = 1 + 9 * 2 * 1 = 1 + 9 * 2 * H10(0)
  • G10(3) = 199 = 1 + 9 * 2 * 11 = 1 + 9 * 2 * H10(1)
  • G10(4) = 1999...9 (de 22 de ori) = 1 + 9 * 2 * 1111...1 (de 22 de ori) = 1 + 9 * 2 * H10(2).

Aici este introdusă o nouă funcţie: G10(N), care nu are o semnificaţie chiar clară, dar putem să deducem recurenţa.

  • H10(0) = 1
  • H10(N) = 1111...1 (de 2 * H10(N - 1) ori)

Generalizând, obţinem:

  • HB(0) = 1
  • HB(N) = 1111...1 (de 2 * HB(N - 1) ori, în baza B)

IV)Formulă pentru 1 + X + X2 + ... + XK

S = 1 + X + X2 + ... + XK
X * S = X + X2 + ... + X(K + 1)
=> (X - 1) * S = X(K + 1) - 1
=> S = (X(K + 1) - 1) / (X - 1)

Astfel, folosind IV), obţinem HB(N) = (B2 * HB(N - 1) - 1) / (B - 1).

Aici intervin mai multe probleme cu operaţia de modulo:

  • Dacă (B - 1) nu este divizibil cu 3, atunci putem să folosim orice tehnică de a calcula inversul modular, aceasta poate fi fie cu algoritmul lui Euclid, fie folosind Teorema lui Euler, metodă folosită şi explicată aici
  • Dacă (B - 1) este divizibil cu 3, nu putem folosi inversul modular la împărţirea cu 3.
  • Dacă B este divizibil cu 3, atunci nu putem folosi teoreme legate de modulo precum Fermat sau Euler.

Dacă B este divizibil cu 3, atunci pe noi ne intereseaza doar ultimele T cifre în baza B, unde M = 3T. Putem folosi un brut, deoarece T este maxim 12.

Dacă B - 1 este divizibil cu 3, atunci putem calcula partea de sus a fracţiei, adică (B2 * HB(N - 1) - 1) modulo (3 * M). Astfel, partea de sus va fi de forma (3 * M) * K + R, R < 3 * M, unde noi cunoaştem doar R, deci (B2 * HB(N - 1) - 1) / 3 = M * K + (R / 3). Pe scurt, ca să calculăm totul modulo M, trebuie să calculăm partea de sus a fracţiei modulo (3 * M), iar după restul pe care îl obţinem sus îl împărţim la 3. Cum B este de forma 3 * K, ca să facem împărţirea şi prin K, folosim metoda inversului modular.

În continuare, pentru a calcula rezultatul modulo M, partea de sus a fracţiei va fi calculată modulo 3 * M sau modulo M, în funcţie de ce caz ne aflăm. Astfel, noi va trebui să folosim teorema lui Euler. Astfel, pentru a calcula B2 * HB(N - 1) modulo M sau 3 * M, va trebui să calculăm B2 * HB(N - 1) modulo phi(M) sau phi(3 * M). Cum M este de forma 3T, atunci phi(M) = 2 * 3T, ba chiar mai mult, phi(phi(M)) = 2 * 3^T ş.a.m.d. Aşadar, în cazul în care B - 1 este divizibil cu 3, putem calcula totul modulo 2 * M. În cazul în care B = 3 * K + 2, atunci, în realitate, vom putea în continuare să calculăm funcţia modulo M, fără să trecem la phi(M), datorită acelui 2 de lângă HB(N - 1).

Ca o scurtă recapitulare, avem grijă în ce caz ne încadrăm, şi după calculăm HB(0), HB(1), ..., HB(N - 2), toate modulo M sau 2 * M . Cum calculăm N - 2 valori diferite ale funcţiei şi avem nişte ridicări în timp logaritmic, complexitatea acestei soluţii va fi O(N * logM).

Soluţie de 100 de puncte

Pentru a calcula HB(N), ne folosim doar de o variabilă, şi anume de HB(N - 1). Dacă la un moment dat în timp ce calculăm şirul HB găsim un element care se repetă, atunci ştim că şirul o să cicleze. Astfel, trebuie calculate doar M elemente, deci complexitatea finală va fi O(M * logM).

Părţile colorate astfel reprezintă cazuri particulare care dacă nu sunt tratate cum trebuie, atunci se pot greşi teste.