Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | interclas.in, interclas.out | Sursă | ad-hoc |
| Autor | Autor necunoscut | Adăugată de |  Sima Cotizo •sima_cotizo |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Interclasare
Se dau doua siruri de numere intregi ordonate crescator, A si B de lungime N, respectiv M. Se cere afisarea unui sir de numere ordonate crescator, care contine elemente atat din sirul A, cat si din B.
Date de intrare
Fişierul de intrare interclas.in va contine pe prima linie N si M, numarul de elemente din cele doua siruri. Pe urmatoarele doua linii se vor afla elementele sirurilor, separate prin spatii.
Date de ieşire
În fişierul de ieşire interclas.out va contine, pe o singura linie, elementele sirului cerut.
Restricţii si precizari
- N+M ≤ 1 000 000
- Elementele din sirurile A si B sunt pozitive si nu vor depasi 20 000 000.
- Elementele din sirurile A si B se pot repeta.
Exemplu
| interclas.in | interclas.out |
|---|---|
| 4 5 1 3 5 9 2 4 6 10 12 | 1 2 3 4 5 6 9 10 12 |
Indicatii de rezolvare
O prima solutie ar presupune citirea datelor intr-un acelasi sir si apoi sortarea acestuia. Complexitatea O((N+M)log(N+M)) nu este insa optima si ar obtine aproximativ 70 de puncte ( o implementare puteti gasi aici ).
Abordarea problemei presupune interclasarea celor doua siruri, operatie ce are complexitatea O(N+M). Vom parcurge sirurile A si B simultan, cu doi iteratori - i si j. La fiecare pas vom introduce in sirul C (cerut de problema) elementul minim dintre A[i] si B[j], avand grija ca iteratorii sa nu fi trecut de numarul de elemente din sir.
Pentru exemplul problemei, primii pasi ai algoritmului pot fi urmatorii:
| Pas 1 | Pas 2 | Pas 3 |
|---|---|---|
 Introduc pe A[i], deci C = (1) |  Introduc pe B[j], deci C = (1,2) |  Introduc pe A[i], deci C = (1,2,3) |
| Pas 4 | Pas 5 | Pas 6 |
 Introduc pe B[j], deci C = (1,2,3,4) |  Introduc pe A[i], deci C = (1,2,3,4,5) |  Introduc pe B[i], deci C = (1,2,3,4,5,6) |
| Pas 7 | Pas 8 | Pas 9 |
 Introduc pe A[i], deci C = (1,2,3,4,5,6,9) |  Cum toate elementele din A au fost parcurse, il introduc pe B[j], deci C = (1,2,3,4,5,6,9,10) |  Introduc pe B[j], deci C = (1,2,3,4,5,6,9,10,12) - raspuns final |
Trebuie avuta in vedere necesitatea memoriei suplimentare la implementare. O prima varianta ar fi declararea sirul C separat, cu N+M elemente si "umplerea" acestuia pe parcurs ( cu sursa aici ). Se poate folosi insa numai max(N,M) memorie suplimentara, considerand ca sirul A are N+M elemente ( o implementare aici ) sau min(N,M) memorie daca se va avea in vedere marirea capacitatii sirului cu mai multe elemente ( cu implementarea aici )
O sursa de 100 de puncte care nu foloseste memorie suplimentara se gaseste aici . De asemenea, o implementare mai scurta a algoritmului se poate gasi aici .
Interclasarea este folosita in cadrul algoritmului merge-sort. Ideea de baza a acestui algoritm este ca un sir de un element este intotdeauna sortat, iar un sir cu lungimea mai mare decat 1 poate fi impartit in jumatati, sortat recursiv si apoi folosit algoritmul de interclasare pentru cele doua jumatati sortate. Puteti incerca rezolvarea problemei din arhiva educationala.
