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

Poveste si cerinta...

Se dau doi vectori de numere intregi: $A$ cu $N$ elemente si $B$ cu $M$ elemente. Sa se afle cel mai lung subsir crescator ce se poate obtine prin interclasarea acestor doi vectori. Reamintim ca o interclasare a doi vectori $A$=($a{~1~}$ , $a{~2~}$, ..., $a{~m~}$) si $B$=($b{~1~}$, $b{~2~}$, ..., $b{~n~}$) este un vector $C$=($c{~1~}$, $c{~2~}$, ..., $c{~m+n~}$) care contine toate elementele lui $A$ si $B$ astfel incat $a{~i~} apare inaintea lui $a{~j~}$ si $b{~i~}$ apare inaintea lui $b{~j~} in $C$ pentru orice $i$<$j$. Prin "subsir crescator" se intelege un subsir $D$=($c{~i{~1~}~}$, $c{~i{~2~}}$, ..., $c{~i{~k~}~}$) astfel incat $i{~1~}$<$i{~2~}$<...<$i{~k~}$ si $c{~i~{~1~}}$<$c{~i~{~2~}}$<...<$c{~i~{~k~}}$.

h2. Date de intrare

...

Pe prima linie a fisierului "interclasare.in" se va afla numarul $N$ reprezentand numarul de elemente ale primului sir. Pe linia a doua se vor afla $N$ numere reprezentand elementului primului sir. Pe linia a treia se va afla numarul $M$ reprezentand numarul de elemente ale celui de-al doilea sir. Pe urmatoarea linie se vor afla cele $M$ elemente ale celui de-al doilea sir.

h2. Date de iesire

...

Pe prima linie a fisierului "interclasare.out" se va afla lungimea celui mai lung subsir crescator ce poate fi obtinut prin interclasarea celor doua siruri din fisierul de intrare. Pe linia a doua se vor afla $N$+$M$ elemente reprezentand sirul $C$, adica sirurile $A$ si $B$ interclasate in asa fel incat cel mai lung subsir comun din vectorul $C$ sa aibe lungime maxima.

h2. Restrictii

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

* $ 1 ≤ $N$,$M$ ≤ 100 000$
* $ 1 ≤ $a{~i~}$ ≤ 100 000$ ptr orice $1$ ≤ $i$ ≤ $N$
* $ 1 ≤ $b{~i~}$ ≤ 100 000$ ptr orice $1$ ≤ $i$ ≤ $M$
* In caz ca exista mai multe solutii afisati oricare dintre ele
* Veti primi punctaje partiale pe fiecare test astfel:
** 40% din punctaj daca prima linie este corecta.
** 100% daca ambele linii sunt corecte
 

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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4
3 9 6 1
5
2 6 4 8 5
|
5
2 3 6 4 8 9 6 1 5

|
h3. Explicatie