Soluție: limba elfică

Știm cu siguranță că o cifră poate reprezenta o literă dacă este diferită de 0 sau poate face parte dintr-un grup de două cifre care reprezintă o literă, dar numai dacă prima cifră din grup este 1 sau 2.

Dacă cifra precedentă este 1, putem forma un grup cu cifra curentă, indiferent care este valoarea acesteia. Dacă cifra precedentă este 2, grupul poate fi format doar dacă cifra curentă este cuprinsă între 0 și 6.

Folosind aceste observații, putem rezolva simplu problema folosind programarea dinamică. La fiecare pas, verificăm dacă cifra curentă poate face parte dintr-un grup (pe baza valorii sale și a valorii cifrei anterioare) sau dacă ea poate reprezenta singură o literă (este diferită de 0).

Așadar, avem cel mult două posibilități de a continua la fiecare pas și numărul variantelor depinde doar de numărul variantelor de la cei doi pași anteriori.

Vom construi un șir nr în care valoarea nri reprezintă numărul textelor care pot fi formate cu primele i cifre. Valoarea nri poate fi calculată folosind valorile nri-1 și nri-2. Practic vom avea nri = α + β, unde α = nri-1 dacă a i-a cifră este diferită de 0 și α = 0 dacă a i-a cifră este 0, iar β = nri-2 dacă a (- 1)-a cifră este 1 sau dacă a (- 1)-a cifră este 2 și a i-a cifră este cel mult egală cu 6 și β = 0 în caz contrar.

Observăm că este posibil să avem α = β = 0; această situația apare dacă avem un șir incorect de cifre (în care un 0 nu urmează după un 1 sau după un 2); un astfel de text nu este corect în limba elfică.

Trebuie să fim atenți când calculăm valorile corespunzătoare primelor poziții. Valoarea nr1 trebuie să fie întotdeauna 1 (am numerotat cifrele începând cu 1), cu excepția cazului în care avem un șir invalid care începe cu 0. Valoarea nr2 poate fi 1 sau 2 în funcție de circumstanțe (dacă a doua cifră poate sau nu face parte dintr-un grup). Valorile următoare pot fi calculate așa cum s-a prezentat anterior. Nu trebuie verificat dacă valorile există (șirul are cel puțin două cifre).

Observăm că va tebui să lucrăm cu numere mari. În cel mai defavorabil caz (secvență care conține doar 1 și 2), numărul variantelor este dată de șirul lui Fibonacci.

Te-ar putea interesa și: