Lampa
Fie xi sirul de cuvinte obtinute. x0 si x1 sunt doua siruri initiale, iar, in rest, avem relatia xi = xi-1 + xi-2, pentru orice i > 1, unde a + b reprezinta concatenarea sirurilor de caractere a si b. Daca ni se da xN trebuie sa determinam x0 si x1. Sa notam x0 = A si x1 = B ( A si B sunt siruri de caractere ). Sirul x va avea forma: A, B, AB, BAB, ABBAB, BABABBAB, etc. Se observa ca numarul de siruri A din al N-lea termen este fibN-2, iar numarul de B este fibN-1, unde fib este sirul lui Fibonacci (fib0 = fib1 = 1 si fibn = fibn-1 + fibn-2 pentru orice n > 1).
Fie M = length(xN). Avem relatia: M = length(A) * fibN-2 + length(B) * fibN-1 (*). Aflam toate solutiile (length(A), length(B)) ale ecuatiei de mai sus. Pentru aceste lungimi A si B sunt unic determinate, in functie de paritatea lui N:
- Daca N este par, A este egal cu primele length(A) caractere din xN si B este egal cu urmatoarele length(B) caractere.
- Daca N este impar, B este egal cu primele length(B) caractere din xN si A este egal cu urmatoarele length(A) caractere.
Pentru A si B determinate verificam in complexitate O(M) daca intr-adevar al N-lea termen al sirului pornind de la A si B este sirul dat si, in caz afirmativ afisam perechea (A B).
Acest algoritm este in practica foarte rapid deoarece fib[N] atinge foarte repede valori mari. Pentru testele date, dupa cum reiesea si din tabelul din restrictiile problemei, avem:
| Test | N | M | Numarul de solutii ale ecuatiei (*) |
|---|---|---|---|
| 1 | 8 | 523 | 5 |
| 2 | 8 | 4200 | 40 |
| 3 | 10 | 5001 | 7 |
| 4 | 9 | 8910 | 32 |
| 5 | 7 | 46189 | 1155 |
| 6 | 6 | 88600 | 5906 |
| 7 | 25 | 346468 | 1 |
| 8 | 14 | 590005 | 17 |
| 9 | 15 | 1010860 | 12 |
| 10 | 17 | 3027197 | 6 |
Se observa ca pe cele 10 teste folosite la corectare O(M) * O(numar_de_solutii_ecuatie) este relativ mic, deci o astfel de rezolvare garanteaza obtinerea punctajului maxim.
