Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2014-02-21 19:47:43.
Revizia anterioară   Revizia următoare  

Gigel şi Resturile

Având în vedere faptul că numărul de pe foaia lui Gigel are maxim 106 cifre în baza B, nu îl putem transforma în baza 10 direct, urmând ca mai apoi să îl împărţim la K. Aşadar, avem un număr A0A1...An-1 în baza B. Îl vom transforma în baza 10, reţinând la fiecare pas doar restul care ne interesează prin procedeul descris în cele ce urmează.

Vom nota cu X numărul pe care dorim să îl obţinem. Iniţializăm X cu 0. Parcurgem cifrele una câte una, începând cu A0. Pentru fiecare cifră Ai, vom înmulţi X cu B şi vom adăuga Ai la X. Având în vedere că nu ne interesează numărul în sine, ci doar restul împărţirii acestuia la K, vom reţine de fiecare dată X modulo K.

Triopalindrom

Un şir de caractere A1A2...A3*k este triopalindrom dacă:

  • A1 = Ak+1, A2 = Ak+2, ..., Ak = A2*k
  • Ak+1 = A2*k+1, Ak+2 = A2*k+2, ..., A2*k = A3*k

Cu alte cuvinte, un şir de caractere A1A2...A3*k este triopalindrom dacă:

  • Ai = Ai+k, pentru oricare 1 ≤ i ≤ 2*k

Pornind de la această observaţie, problema revine la setarea lungimii k a şirului de caractere şi la parcurgerea caracterelor de la primul către ultimul. Pentru fiecare poziţie i, vom verifica dacă Ai = Ai+k. În momentul în care dăm peste 2*k poziţii consecutive care respectă această proprietate, este evident că am dat peste o secvenţă de tip triopalindrom, deci o vom număra. Complexitate: O(N2).