Interclasare

interclasare

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

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~}~}$ &le; $c{~i{~2~}~}$ &le;...&le; $c{~i{~k~}~}$.

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

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$} numere 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.

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$ ≤ $10 000$
* $0$ ≤ $a{~i~}$ ≤ $30 000$ ptr orice $1$ ≤ $i$ ≤ $N$
* $0$ ≤ $b{~i~}$ ≤ $30 000$ ptr orice $1$ ≤ $i$ ≤ $M$

* $ 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$% din punctaj daca ambele linii sunt corecte

** 40% din punctaj daca prima linie este corecta.
** 100% daca ambele linii sunt corecte

h2. Exemplu

| 4
3 9 6 1
5

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

2 6 4 8 5
|
5
2 3 6 4 8 9 6 1 5
|
 
h3. Explicatie
 
...

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

2205