Fişierul intrare/ieşire:interclasare.in, interclasare.outSursăLista lui Francu
AutorCatalin FrancuAdăugată dedevilkindSavin Tiberiu devilkind
Timp execuţie pe test0.15 secLimită de memorie9216 kbytes
Scorul tăuN/ADificultateN/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=( a1 , a2, ..., am) si B=( b1, b2, ..., bn ) este un vector C=( c1 , c2, ..., cm+n ) care contine toate elementele lui A si B astfel incat ai apare inaintea lui aj si bi apare inaintea lui bj in C pentru orice i < j . Prin "subsir crescator" se intelege un subsir D=( ci1, ci2, ..., cik) astfel incat i1<i2<...<ik si ci1ci2 ≤...≤ cik.

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

  • 1N , M10 000
  • 0ai30 000 ptr orice 1iN
  • 0bi30 000 ptr orice 1iM
  • 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

interclasare.ininterclasare.out
4
3 9 6 1
5
2 6 4 8 5
5
2 3 6 4 8 9 6 1 5
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content