==Include(page="template/taskheader" task_id="bifo")==
==Include(page="template/raw")==
bifo
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 n >= 3, 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. 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 Iesire
Fisierul de iesire bifo.out va contine pe prima linie un sir de M caractere reprezentand formula leacului miraculos.
h2. Restrictii si precizari
S 1 <= M <= 100;
S A[1] si A[2] contin doar litere mici ale alfabetului englez;
S Numerotarea pozitiilor din sirul infinit incepe cu 1;
S Cele M pozitii vor fi numere intregi (nu neaparat distincte) de maxim 100 de cifre;
S Pentru 60% din teste pozitiile vor fi numere intregi intre 1 si 1.000.000.000;
S 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 |explicatii |
|ab |xdb |Primele 5 siruri de caractere obtinute folosind "formula bifo" sunt:|
| | | |
|cdx | |ab, cdx, abcdx, cdxabcdx, abcdxcdxabcdx |
| | | |
|3 | | |
| | | |
|10 | |Concatenand aceste siruri se obtine sirul magic: |
| | | |
|4 | |abcdxabcdxcdxabcdxabcdxcdxabcdx... |
| | | |
|15 | | |
==Include(page="template/taskheader" task_id="bifo")==
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. 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 Iesire
Fisierul de iesire $bifo.out$ va contine pe prima linie un sir de $M$ caractere reprezentand formula leacului miraculos.
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
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")==
