Fişierul intrare/ieşire:seif.in, seif.outSursăStelele Informaticii 2007-2008, Clasele 11-12
AutorAndrei GrigoreanAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Seif

Miruna a ajuns intr-o mare incurcatura. Deoarece urma sa aiba examen la algoritmi si structuri de date, s-a hotarat sa dea o spargere in apartamentul profesorului sau pentru a pune mana pe subiecte. La inceput s-a descurcat bine, insa acum se afla in fata seifului ce pastreaza mult ravnitele subiecte de examen. Pentru a trece de acest ultim obstacol, Miruna trebuie sa introduca un cod secret. Ea a aflat din surse sigure ca acest cod are lungimea mai mare sau egala decat un numar K. Deasemenea, a mai facut rost din biroul profesorului de 2 siruri de litere mari ale alfabetului de lungimi N si M. Miruna banuieste ca parola secreta ce deschide seiful este un subsir comun al celor 2 siruri, cat mai mare lexicografic.

Cerinta

Stiind cele 2 siruri si numarul K, aflati subsirul comun de lungime mai mare sau egala cu K cat mai mare lexicografic.

Date de intrare

Pe prima linie a fisierului de intrare seif.in se gaseste un numar intreg T, reprezentand numarul de teste. Fiecare test este compus din 3 linii: pe prima linie se gaseste un numar intreg K, iar urmatoarele 2 linii contin sirurile de caractere.

Date de iesire

Fisierul de iesire seif.out va contine T linii, pe fiecare linie aflandu-se subsirul cautat pentru fiecare test in parte.

Restrictii

  • 1 ≤ T ≤ 10
  • 1 ≤ N, M ≤ 1000
  • 0 ≤ K ≤ min(N, M)
  • Un sir (x1,x2...xN) este mai mare din punct de vedere lexicografic decat un alt sir (y1,y2...yM) daca exista o pozitie p astfel incat xp > yp si x1 = y1, x2 = y2 ... xp-1 = yp-1.
  • Pentru datele de test exista intotdeauna solutie

Exemplu

seif.inseif.out
2
2
AAZ
AZA
1
ZAZ
ZBZ
AZ
ZZ
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content