== include(page="template/taskheader" task_id="bifo") ==
==Include(page="template/taskheader" task_id="bifo")==
Poveste ...
Pentru a-si vindeca rana provocata de Spanul cel Negru, printul Algorel are nevoie de leacul miraculos aflat in posesia vrajitoarei din padurea intunecata. Aceasta i-a promis leacul daca ii rezolva urmatoarea problema, la care ea s-a gandit zadarnic o mie de ani: pornind de la doua cuvinte initiale $A{~1~}$ si $A{~2~}$ si aplicand "formula bifo" $A{~n~} = A{~n-2~}A{~n-1~}$ pentru {$3 ≤ n$}, se obtin cuvintele $A{~3~}, A{~4~}, A{~5~}$ s.a.m.d. Prin $A{~n-2~}A{~n-1~}$ intelegem concatenarea cuvintelor $A{~n-2~}$ si $A{~n-1~}$ in aceasta ordine. Toate aceste cuvinte ({$A{~1~} A{~2~}, A{~3~} A{~4~}, A{~5~}$} s.a.m.d), sunt la randul lor concatenate, in ordine, formand un sir de caractere infinit denumit sir magic. Formula leacului miraculos are $M$ caractere, pe care vrajitoarea nu le stie. Se stiu insa cele $M$ pozitii din sirul magic in care apar, in ordine, caracterele din formula.
h2. Cerinta
...
Cu toata inteligenta lui, Algorel nu poate rezolva aceasta problema. Ajutati-l pe print sa iasa din incurcatura afland formula leacului magic.
h2. Restrictii
h2. Date de Intrare
...
Primele doua linii ale fisierului $bifo.in$ contin fiecare cate un sir de cel mult $100$ de caractere reprezentand cuvintele $A{~1~}$ (pe prima linie) si respectiv $A{~2~}$ (pe a doua linie). A treia linie contine un numar intreg {$M$}, reprezentand numarul de caractere din formula leacului miraculos. Urmeaza $M$ linii descriind, in ordine, pozitiile din sirul magic unde se gasesc caracterele din formula.
h2. Date de intrare
h2. Date de Iesire
...
Fisierul de iesire $bifo.out$ va contine pe prima linie un sir de $M$ caractere reprezentand formula leacului miraculos.
h2. Date de iesire
h2. Restrictii si precizari
...
* $1 ≤ M ≤ 100$
* $A{~1~}$ si $A{~2~}$ contin doar litere mici ale alfabetului englez
* Numerotarea pozitiilor din sirul infinit incepe cu $1$
* Cele $M$ pozitii vor fi numere intregi (nu neaparat distincte) de maxim $100$ de cifre
* Pentru $60%$ din teste pozitiile vor fi numere intregi intre $1$ si $1.000.000.000$
* Fiecare linie din fisierul de intrare si din fisierul de iesire se termina cu marcaj de sfarsit de linie
h2. Exemplu
| bifo.in | bifo.out |
| linia1
linia2
linia3
| linia1
linia2
|
table(example). |_. bifo.in |_. bifo.out |
| ab
cdx
3
10
4
15
| xdb |
h3. Explicatii
Primele 5 siruri de caractere obþinute folosind formula bifo sunt:
*ab, cdx, abcdx, cdxabcdx, abcdxcdxabcdx*
Concatenand aceste siruri se obþine sirul magic:
{*abcdxabcdxcdxabcdxabcdxcdxabcdx*}...
== include(page="template/taskfooter" task_id="bifo") ==
==Include(page="template/taskfooter" task_id="bifo")==
