  |
 |
 
Cu speranta ca n-am facut vreo gafa, iata problema 39. Spor la lucru! PROBLEMA 39: INTERCLASARE DEADLINE: Miercuri, 26 ianuarie 2000 DOMENIU: Dinamica, ce altceva :) TIMP DE IMPLEMENTARE: 1h 30' PUNCTAJ: 50 dex Se dau doi vectori de numere intregi: A cu m elemente si B cu n 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(i1), c(i2), ..., c(ik)) astfel incat i1<i2<...<ik si c(i1)<=c(i2)<=...<=c(ik). DATE DE INTRARE: Fisierul VECTORI.IN are formatul: m a(1) a(2) ... a(m) n b(1) b(2) ... b(n) Restrictii: 1<=m,n<=200, 0<=a(i), b(j)<= 30000 DATE DE IESIRE: In fiserul VECTORI.OUT se va tipari pe prima linie lungimea celui mai lung subsir crescator pe care il poate contine o interclasare bine aleasa a vectorilor A si B. Pe a doua linie se va tipari un vector de lungime m+n rezultat din interclasarea lui A si a lui B si care contine un subsir crescator de lungimea calculata. EXEMPLU: Exemplu: VECTORI.IN VECTORI.OUT 4 5 3 9 6 1 2 3 6 4 8 9 6 1 5 5 2 6 4 8 5 Explicatie: A si B pot fi interclasati in vectorul C=(2, 3, 6, 4, 8, 9, 6, 1, 5), care contine subsirul crescator (2, 3, 4, 8, 9) de lungime 5. Deoarece A si B nu pot fi interclasati pentru a produce un subsir crescator de lungime mai mare decat 5, raspunsul este 5. Asta daca nu cumva am gresit iarasi exemplul. COMPLEXITATE RECOMANDATA: O[m*n*(m+n)] TIMP DE RULARE: O secunda. Corectarea se va face pe un Celeron @400 cu 128MB RAM. Asteptam aplauze extaziate :) Observatii: Corectarea se va face candva pe la sfarsitul lui ianuarie. Desi se cere numai lungimea subsirului, este un exercitiu bun sa incercati sa produceti si o interclasare efectiva. |
|
 |
|