Bazandu-ne pe acelasi principiu ca si cel anterior, constatam ca putem retina o tabela de dispersie / tabela hash pentru toate momentele de timp in care s-a pariat. Pentru fiecare moment de timp vom retine in hash valoarea de bani castigata de cei $N$ oameni. In final, vom afisa doar momentele de timp care exista in hash.

h2. 'Melodii':problema/melodii
 
Problema se poate reformula matematic in modul urmator:
 
* Care este numarul de posibilitati de a scrie numarul $N$ ca suma de $1$ si $2$?
 
Genul acesta de probleme care cer numarul de posibilitati de a se intampla un eveniment ce este reprezentat in input printr-o singura valoare se rezolva in general prin doua moduri. Problema de fata se poate rezolva prin ambele abordari:
 
* Se genereaza (de mana, sau se creeaza un mic programel, eventual cu backtracking) rezultatele pentru date de intrare mici si se incearca gasirea unei relatii de recurenta sau a unei formule in functie de indexul valorii in sir. In acest caz sirul rezultat este urmatorul (fara modulo) - $1 2 3 5 8 13 21 34 55 89$ ... Pentru cei care nu cunosc acest sir, acesta se numeste sirul lui Fibonacci si are aplicabilitati in matematica si informatica deopotriva.
 
* Se incearca gasirea unei recurente folosind metoda programarii dinamice. In acest caz recurenta este in felul urmator: numarul de moduri de a scrie $N$ ca suma de $1$ si $2$ este numarul de moduri de a scrie $N-2$ la care se adauga valoarea $2$ la final pentru fiecare mod posibil + numarul de moduri de a scrie $N-1$ la care se adauga valoarea $1$ la final. In acest mod se acopera toate solutiile posibile si nu se amesteca intre ele. Matematic vorbind recurenta arata in felul urmator : $Best[i] = Best[i-2] + Best[i-1]$. Se observa din nou ca aceasta recurenta corespunde sirului lui Fibonacci.
 
In acest mod am redus problema la a afla rapid care este al $N+1$-lea termen din sirul lui Fibonacci. Spunem al $N+1$-lea termen deoarece sirul lui Fibonacci incepe cu valorile $1 1 2$, iar sirul nostru incepe cu $1 2 3$.
 
Vom descrie in continuare $5$ solutii cu timpi de executie diferiti, dar care rezolva corect problema.
 
h4. $Solutia 1: O(N*2^N) pe fiecare din cele T teste - 10 puncte$
 
Se genereaza cu backtracking fiecare secventa posibila de a scrie valoarea $N$ ca suma de $1$ si $2$ si se numara
aceste secvente.
 
h4. $Solutia 2: O(N) pentru fiecare din cele T teste - 30 puncte$
 
Se calculeaza pentru fiecare din cele $T$ teste al $N+1$-lea termen Fibonacci.
 
h4. $Solutia 3: O(MaxValue) - 50 puncte$
 
Se preproceseaza sirul lui Fibonacci pana $1 milion$ si se raspunde in $O(1)$ la fiecare din cele $T$ teste.
 
h4. $Solutia 4: O(8*log(N)) pe fiecare din cele T teste - 70 puncte$
 
Se foloseste ridicarea la putere in timp logaritmic a matricei $((0,1),(1,1))$, asa cum este prezentat in articolul acesta: 'Al k-lea termen Fibonacci':problema/kfib.
 
h4. $Solutia 5: O(R + T) - 100 puncte$
 
Sirul lui Fibonacci este periodic modulo un numar natural. Se calculeaza perioada pentru valoarea $R$ si apoi se genereaza sirul lui Fibonacci pana la acea perioada. Vom nota valoarea perioadei cu $PER$. Raspunsul pentru un numar $N$ va fi a $((N+1)%PER)$-a valoare din sirul lui Fibonacci.
 
Pentru modul in care putem calcula perioada ne uitam de exemplu la ultima cifra a numerelor din sir (adica modulo 10) si putem observa ca momentul in care incep numerele sa se repete este cand apar valorile $0$ si $1$ alaturate in sir. Astfel putem genera sirul lui Fibonacci modulo $R$ pana cand gasim valorile $0$ si $1$ alaturate. Perioada pentru valoarea $R$ nu va depasi niciodata valoarea $4*R$, pentru orice $R$ numarul natural.
 

h2. 'Camionas':problema/camionas
h4. $Solutia 1: O(M * log N) - 100 puncte$