.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » bifo

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
bifo


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
2MB / 1MB

Pentru a-şi vindeca rana provocată de Spânul cel Negru, prinţul Algorel are nevoie de leacul miraculos aflat în posesia vrăjitoarei din pădurea întunecată. Aceasta i-a promis leacul dacă îi rezolvă următoarea problemă, la care ea s-a gândit zadarnic o mie de ani: pornind de la două cuvinte iniţiale A1 şi A2 şi aplicând „formula bifo” An = An-2An-1 pentru n ≥ 3, se obţin cuvintele A3, A4, A5, ş.a.m.d. Prin An-2An-1 înţelegem concatenarea cuvintelor An-2 şi An-1 în această ordine. Toate aceste cuvinte (A1, A2, A3, A4, A5 ş.a.m.d), sunt la rândul lor concatenate, în ordine, formând un şir de caractere infinit denumit şir magic. Formula leacului miraculos are M caractere, pe care vrăjitoarea nu le ştie. Se ştiu însă cele M poziţii din şirul magic în care apar, în ordine, caracterele din formulă.

Cerinţă

Cu toată inteligenţa lui, Algorel nu poate rezolva această problemă. Ajutaţi-l pe prinţ să iasă din încurcătură aflând formula leacului magic.

Date de intrare

Primele două linii ale fişierului de intrare bifo.in conţin fiecare câte un şir de cel mult 100 de caractere reprezentând cuvintele A1 (pe prima linie) şi respectiv A2 (pe a doua linie). A treia linie conţine un număr întreg M, reprezentând numărul de caractere din formula leacului miraculos. Urmează M linii descriind, în ordine, poziţiile din şirul magic unde se găsesc caracterele din formulă.

Date de ieşire

Fişierul de ieşire bifo.out va conţine pe prima linie un şir de M caractere reprezentând formula leacului miraculos.

Restricţii

1 ≤ M ≤ 100;
A1 şi A2 conţin doar litere mici ale alfabetului englez;
Numerotarea poziţiilor din şirul infinit începe cu 1;
Cele M poziţii vor fi numere întregi (nu neapărat distincte) de maxim 100 de cifre;
Pentru 60% din teste poziţiile vor fi numere întregi între 1 şi 1000000000;
Fiecare linie din fişierul de intrare şi din fişierul de ieşire se termină cu marcaj de sfârşit de linie;

Exemple

bifo.inbifo.outExplicaţii
ab cdx 3 10 4 15 xdb Primele 5 şiruri de caractere obţinute folosind „formula bifo” sunt:
ab, cdx, abcdx, cdxabcdx, abcdxcdxabcdx

Concatenând aceste şiruri se obţine şirul magic:
abcdxabcdxcdxabcdxabcdxcdxabcdx...

autor: Silviu Gănceanu
propunător: Prof. Marinel Şerban
Liceul de Informatică “Grigore Moisil”
marinel_serban@yahoo.com
Articole recomandate
Probleme recomandate
De la ONI 2005: baschet, ingerasi, numar1, prieteni, robinson, aritma, cezar, cuburi2, joc8, joc9, pal, romeo, seceta, antena, avere, joc11, paianjen, suma2, vizibil, masina3, csir, lsort, patrat, ziduri, anticip, bsir, evantai, galax, spion, texan
De acelaşi autor: descfib, otilia, tvshow, algola, pal, evantai, treegame
Despre şiruri de caractere: scp, ab, sl, nrcuv, rv, kpal, chimie, reteta, replace, grad, index, cod, text, decript, spam, complex, cifre, anagrame, balbe, criptmat, mesaj, maxim, astre, sablon, formule, ed, balls, vocale, prop, bacan, novel, bitslang, text2, ref, scor2, convert, cod2, compress, pstring, sub, rima, program1, sms, circular, randuri, cezar, joc9, pal, bare, joc12, fractie, cod3, tunel, csir, top, ratina, cifru1, limbaj, adun, ecuatii, dir, paritate, virus, sir6, mesaj2, text1, sirul, ogorul, rez, sablon1, anag, sir8, seti, secvsir, dp, cuvant, strings, antipatie, fractie1, links, ordonare, text3, concat, codif, cheie, alfabetar, cuvinte2, comp, litere, mxl, mesaj3, expresie2, grad2, antic, zuma, expeval, combcuv, lgdrum, subtitrare, compresie, zigzag, azeval, fraze, subsecvente, showroom, rebus1, agenda, opmult, betisoare, reziston, clase, vot2, ecp, smiley, charlie, cript, scadere, spioni1, sablon3, expand, culori3, virgule
Despre vector: trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, oras, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig
Despre numere mari: fib, 2sir, test, sort, gray, siruri, vecini, div, sir2, nrcuv2, scor, hanoig, red, matrice3, pavaj, depou, pm, sqr, set, albine, teatru1, descfib, tub, m01, soldati1, euclid, mutare, munte1, banda10, sg1, cutii, zumzi, numere7, trapez, patrate6, muguri, impozit, kbiti, m4, numar3, parbit, petrecere, randomizare, radical, ghinion, aliniere, sumb, cavaleri, camera616, numar4, pavari, asfalt, rotund, cos, risipa, xpn, dale, codpatrat, culori1, plus, minm, pomi, cifrab, subsets, doitrei, conjectura, ech, inventie
Chestionare recomandate
surse trimise | ajutor