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, obtinut prin concatenarea sirurilor A si 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
- 1 ≤ N, M ≤ 900 000
- 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.
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) |
Sursa de 100 de puncte se gaseste aici . De asemenea, o implementare mai scurta a algoritmului se poate gasi aici .
