Fişierul intrare/ieşire:stradacramei.in, stradacramei.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 18
AutorVlad-Andrei MunteanuAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test6 secLimită de memorie64000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Strada Cramei

Dupa ce anul trecut cei doi scelerati si-au facut de cap zile intregi cu licoarea magica, Russky, anul acesta nu vor sa se lase mai prejos si isi propun sa epuizeze stocurile magazinelor de pe Strada Cramei de-a lungul a n zile. Pe aceasta strada se afla m magazine aflate in linie si numerotate de la 1 la m, fiecare dintre acestea fiind aprovizionat cu un singur tip de bautura dintre milioanele existente in lume. Deoarece nu vor sa ramana fara fonduri, cei doi scelerati isi propun sa epuizeze stocul unui singur magazin pe zi. Primul scelerat insa, se simte mult mai experimentat si mai dornic de senzatii tari, asa ca isi doreste ceva mult mai rafinat. Pentru a obtine asta, si-a notat pe o hartie o secventa de n cifre, litere mici si litere mari ale alfabetului englezesc, caracterul de la pozitia i reprezentand codul bauturii pe care acesta trebuie sa o bea in ziua i pentru a-si satisface nevoile. Cel de-al doilea scelerat are si el dorintele sale proprii pentru a se bucura la maxim de aceasta noua experienta si fara costuri prea ridicate, asa ca ii cere camaradului sau ca amandoi sa plece de la acelasi magazin in prima zi, iar apoi, in fiecare dintre cele n zile, sa epuizeze stocul magazinului curent si sa se mute la magazinul imediat urmator. Din pacate, in drumul lor catre placere, primul scelerat isi pierde lista, asa ca nu ii ramane altceva decat sa incerce sa o refaca pe loc. Deoarece era sub influenta licorii magice atunci cand a scris-o prima data, acesta nu reuseste sa isi aminteasca exact ce cod avea fiecare bautura din fiecare zi si se decide sa puna un semn de intrebare in dreptul fiecarei zile in care nu este sigur, asta insemnand ca in acea zi este dispus sa bea orice fel de bautura. Deoarece dorinta celui de-al doilea scelerat este indeplinita de la sine, cei doi vor sa plece de la un magazin astfel incat lista nou generata de primul scelerat sa fie respectata intocmai. Deoarece amandoi sunt foarte obositi in urma calatoriei si singurul lucru pe care si-l doresc este sa se relaxeze, se gandesc sa va ceara ajutorul. Stiindu-va insa atat de buni programatori, acestia nu se multumesc numai cu indicele unui magazin de unde ar trebui sa plece, ci va cer sa le spuneti din dreptul cator magazine pot pleca in ziua 1 astfel incat sa respecte cu strictete lista.

Date de intrare

Fisierul de intrare stradacramei.in contine pe prima linie un sir de caractere, s, reprezentand lista nou generata a primului scelerat, iar pe a doua linie un sir de caractere t, reprezentand configuratia magazinelor de pe Strada Cramei.

Date de ieşire

Fisierul de iesire stradacramei.out va contine pe prima linie numarul de magazine de unde cei doi scelerati pot porni in prima zi astfel incat sa se respecte lista.

Restricţii

  • 1 ≤ n ≤ 200.000
  • 1 ≤ m ≤ 200.000

Exemplu

stradacramei.instradacramei.out
a?1a
ab1aa1aAc1a
2

Explicaţie

Cei doi scelerati isi pot incepe aventura de la magazinul 1 sau de la magazinul 4.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?