harddp

HardDP

== include(page="template/taskheader" task_id="harddp") ==

Poveste şi cerinţă...

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.

h2. Date de intrare

Fişierul de intrare $harddp.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $harddp.out$ ...

Î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$.

h2. Restricţii

* $... ≤ ... ≤ ...$

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

h2. Exemplu
table(example). |_. harddp.in |_. harddp.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

|1
3
100
|011
|

== include(page="template/taskfooter" task_id="harddp") ==