Fişierul intrare/ieşire:harddp.in, harddp.outSursăConcursul National de Informatica "Adolescent Grigore Moisil"
AutorFlorin ChiricaAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Harddp

Sorin a citit de curand “Legendele Olimpului”, carte ce i-a deschis calea catre un maret destin. Asemeni lui Orfeu in cautarea lui Euridice, acesta porneste in calatoria sa initiatica cunoscuta drept “mitul coborarii in beci”. Calea sa il poarta pe urmele algoritmului celui mai lung subsir comun. Usa grea din lemn se inchide in spatele sau.

Comisia lumii subterane ii da un sir A de N caractere de 0 si 1. El trebuie sa gaseasca un sir B, de lungime N, format tot din 0 si 1, astfel incat lungimea celui mai lung subsir comun dintre A si B sa fie minima. Ajuta-l pe Sorin sa transceada catre stadiul olimpic prin rezolvarea problemei.

Date de intrare

Fişierul de intrare harddp.in va contine pe prima linie un numar natural T, reprezentand numarul de teste. A doua linie contine N, numar intreg. A treia linie contine un sir binar de caractere de lungime N (fara spatii intre caractere). Structura testului se repeta de T ori.

Date de ieşire

În fişierul de ieşire harddp.out vor fi T linii, cate una pentru fiecare test. O linie contine un sir de caractere binar de lungime N.

Restricţii

  • 1 ≤ T ≤ 75
  • 1 ≤ N ≤ 1000
  • Va rugam sa nu spuneti comisiei ce ar spune Sorin!

Exemplu

harddp.inharddp.out
1
3
100
011
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?