Melodii
Solutii prezentate de 
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.
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.
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.
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.
Solutia 4: O(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.
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.
