| Fişierul intrare/ieşire: | harddp.in, harddp.out | Sursă | Concursul National de Informatica "Adolescent Grigore Moisil" |
| Autor | Florin Chirica | Adăugată de |  AGMInformatica •AGMinformatica |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
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.in | harddp.out |
|---|---|
| 1 3 100 | 011 |
