Pagini recente » Istoria paginii utilizator/gizas46 | Bcolor | Istoria paginii utilizator/vlad3108 | Istoria paginii utilizator/upb_darius_rares_silviu | Password1

Fişierul intrare/ieşire:	password1.in, password1.out	Sursă	RMI 2015
Autor	Mihai Andreescu	Adăugată de	Bogdan Ciobanu •bciobanu
Timp execuţie pe test	1 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

Password1

Din cauza paranoiei legate de securitate, Sam s-a decis să aleagă o parolă lungă pentru contul său de e-mail care să conţină doar litere mici ale alfabetului englez. Totuşi, el a realizat că există un mare risc să-şi uite parola, aşa că s-a decis să o codifice în două şiruri, care de asemenea conţin doar litere mici ale alfabetului englez. El a scris aceste şiruri pe o foaie de hârtie, pe care a ascuns-o sub patul său. Sam a ales şirurile A şi B astfel încât parolă S este o anagramă a lui B care apare ca subşir în A şi care este minimă lexicografic.

Se consideră că un şir $B = B_{1}B_{2}..B_{|B|}$ este un subşir al lui $A = A_{1}A_{2}...A_{|A|}$ dacă şi numai dacă există un şir de indici strict crescători $n_{1}, n_{2}, ..., n_{|B|}$ astfel încât $A_{n_i} = B_{i}$ pentru $i \in [1..|B|]$ .

Spunem că A este mai mic lexicografic decât B dacă şi numai dacă există un index $n<|A|$ astfel încât $A_{i} = B_{i}$ pentru $i \in [1..n]$ şi $A_{n+1}< B_{n+1}$ .

Cum era de aşteptat, Sam şi-a uitat parola după o săptămâna şi acum se chinuie să o recupereze, motiv pentru care apelează la voi pentru ajutor. Scrieţi un program care îi găseşte parola.

Date de intrare

Fişierul de intrare password1.in conţine exact două şiruri A şi B separate printr-un singur spaţiu alb.

Date de ieşire

Fişierul de ieşire password1.out trebuie să conţină o linie reprezentând parola lui Sam. În caz că nu există soluţie, se va afişa cuvântul "impossible" (fără ghilimele).