== include(page="template/taskheader" task_id="interclas") ==

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$.

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$.

h2. Date de intrare

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.

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:

|!problema/interclas?p3.JPG!
Introduc pe $A[i]$, deci $C = (1,2,3)$|

Sursa de 100 de puncte se gaseste 'aici':job_detail/261348?action=view-source . De asemenea, o implementare mai scurta a algoritmului se poate gasi 'aici':job_detail/261349?action=view-source .

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':http://infoarena.ro ). Se poate folosi insa numai $max(N,M)$ memorie suplimentara, considerand ca sirul $A$ are $N+M$ elemente ( o implementare 'aici':http://infoarena.ro ) sau $min(N,M)$ memorie daca se va avea in vedere marirea capacitatii sirului cu mai multe elemente ( cu implementarea 'aici':http://infoarena.ro )
 
O sursa de 100 de puncte care nu foloseste memorie suplimentara se gaseste 'aici':job_detail/261348?action=view-source . De asemenea, o implementare mai scurta a algoritmului se poate gasi 'aici':job_detail/261349?action=view-source .
 
Interclasarea este folosita

== include(page="template/taskfooter" task_id="interclas") ==