Fișierul bac.in conține numere naturale: pe prima linie două numere din intervalul [1,106], m și n, pe
a doua linie un șir de m numere din intervalul [1,109], iar pe a treia linie un șir de n numere din
intervalul [1,109]. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu, și
ambele șiruri sunt ordonate crescător.
Se cere să se afișeze pe ecran, în ordine strict crescătoare, un șir format dintr-un număr maxim de
termeni care aparțin cel puțin unuia dintre cele două șiruri, astfel încât oricare două elemente aflate pe
poziții consecutive să fie de paritate diferită. Numerele afișate sunt separate prin câte un spațiu.
Proiectați un algoritm eficient din punctul de vedere al timpului de
executare.
Exemplu: dacă fișierul are conținutul alăturat, se afișează pe ecran
2 3 4 5 8 11 14 sau 2 3 4 5 10 11 14
8 5
2 4 5 8 8 11 14 14
3 4 5 5 10
Răspunsuri la întrebare
Răspuns:
#include <iostream>
#include<fstream>
using namespace std;
ifstream f("bac.txt");
int m,n,a[1000001],mini,i,j,ultim,x;
int main()
{
ultim=-1;
f>>m>>n;
for(i=1; i<=m; i++)
f>>a[i];
i=1;
j=1;// parcurg numerele de la 1 la n
f>>x;
while(i<=m and j<=n)
{
mini=min(x,a[i]);
if(ultim==-1)
{
cout<<mini<<" ";
ultim=mini;
}
else if(ultim%2!=mini%2)
{
cout<<mini<<" ";
ultim=mini;
}
if(x==mini and a[i]==mini)
{
i++,j++;
f>>x;
}
else if(x!=mini and a[i]==mini)
i++;
else
{
j++;
f>>x;
}
}
while(i<=m)
{
if(ultim%2!=a[i]%2)
{
cout<<a[i]<<" ";
ultim=a[i];
}
i++;
}
while(j<=n)
{
f>>x;
j++;
if(ultim%2!=x%2)
{
cout<<x<<" ";
ultim=x;
}
}
return 0;
}
Explicație:
Algoritmul realizeaza interclasarea celor doua siruri de numere. Citesc mai intai m si n, apoi cele m elemente, pe care le memorez in a[1...m]. Citesc mai intai primul element din al doilea sir, dupa care dau drumul interclasarii. Realizez citirea unui nou element din al doilea sir doar daca este nevoie (de asta nu pot parcurge cu un for). Dpdv al timpului de executare, algoritmul este eficient, deoarece parcurge o singura data(de fapt parcurge primul sir de doua ori, o data la citire si dupa la interclasare) elementele din fisier==> complexitate liniara= O(2*m+n)
De asemenea, puteam sa realizez interclasarea normala, cu 2 sau chiar 3 vectori, deoarece se metioneaza ca este nevoie doar de eficienta ca timp. Insa nu este mare diferenta la cod.