Fişierul intrare/ieşire: | bifo.in, bifo.out | Sursă | ONI 2005, clasa a 9-a |
Autor | Silviu-Ionut Ganceanu | Adăugată de | |
Timp execuţie pe test | 0.2 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
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 A1 si A2 si aplicand "formula bifo" An = An-2An-1 pentru 3 ≤ n, se obtin cuvintele A3, A4, A5 s.a.m.d. Prin An-2An-1 intelegem concatenarea cuvintelor An-2 si An-1 in aceasta ordine. Toate aceste cuvinte (A1 A2, A3 A4, A5 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.
Cerinta
Cu toata inteligenta lui, Algorel nu poate rezolva aceasta problema. Ajutati-l pe print sa iasa din incurcatura afland formula leacului magic.
Date de Intrare
Primele doua linii ale fisierului bifo.in contin fiecare cate un sir de cel mult 100 de caractere reprezentand cuvintele A1 (pe prima linie) si respectiv A2 (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.
Date de Iesire
Fisierul de iesire bifo.out va contine pe prima linie un sir de M caractere reprezentand formula leacului miraculos.
Restrictii si precizari
- 1 ≤ M ≤ 100
- A1 si A2 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
Exemplu
bifo.in | bifo.out |
---|---|
ab cdx 3 10 4 15 | xdb |
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...