Fişierul intrare/ieşire:password1.in, password1.outSursăRMI 2015
AutorMihai AndreescuAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test2.0 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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).

Restricţii

  •  1 \leq |A| \leq 3 * 10^7
  •  1 \leq |B| \leq 3 * 10^6

Exemplu

password1.inpassword1.out
abacaba bababb
abacaba cbcimpossible
abacaba caabaacb
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?