Fişierul intrare/ieşire:	interclasare.in, interclasare.out	Sursă	Lista lui Francu
Autor	Catalin Francu	Adăugată de	Savin Tiberiu •devilkind
Timp execuţie pe test	0.075 sec	Limită de memorie	9216 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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₁ , a₂, ..., a_m) si B=( b₁, b₂, ..., b_n ) este un vector C=( c₁ , c₂, ..., 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_i1, c_i2, ..., c_ik) astfel incat i₁<i₂<...<i_k si c_i1 ≤ c_i2 ≤...≤ c_ik.

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.

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.

Restrictii

• 1 ≤ N , M ≤ 10 000
• 1 ≤ a_i ≤ 30 000 ptr orice 1 ≤ i ≤ N
• 1 ≤ b_i ≤ 30 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

Exemplu

Cum se trimit solutii?