fbpx

Problema #241 – Interclasare – Rezolvari PBInfo

de Mihai-Alexandru

Cerinţa

Se dau două şiruri a şi b, cu n, respectiv m elemente, numere naturale, ordonate crescător. Să se construiască un al treilea şir, c, care să conţină, în ordine crescătoare, elementele din şirurile a şi b.

Date de intrare

Fişierul de intrare interclasare.in conţine pe prima linie numărul n; urmează n numere naturale, ordonate crescător, ce pot fi dispuse pe mai multe linii. Linia următoare conţine numărul m şi urmează m numere naturale, ordonate crescător, ce pot fi dispuse pe mai multe linii.

Date de ieşire

Fişierul de ieşire interclasare.out va conţine elementele şirului construit, câte 10 valori pe o linie, elementele de pe o linie fiind separate printr-un spaţiu. Ultima linie a fişierului poate să conţină mai puţin de 10 valori.

Restricţii şi precizări

  • 1 ≤ n, m ≤ 100.000
  • valorile elementelor celor două şiruri vor fi mai mici decât 1.000.000

Exemplu

interclasare.in

7
1 3 4 6
7 8 8 
8
2 4 5 6 8
9 9 12

interclasare.out

1 2 3 4 4 5 6 6 7 8 
8 8 9 9 12 
#include <bits/stdc++.h>

using namespace std;

ifstream cin("interclasare.in");
ofstream cout("interclasare.out");

int main()
{
    int n, m, k = 0;
    int a[100001], b[100001], c[200001];
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    cin >> m;
    for(int i = 1; i <= m; ++i)
        cin >> b[i];

    int i = 1, j = 1;

    while(i <= n && j <= m)
        if(a[i] < b[j])
            c[++k] = a[i], i++;
        else
            c[++k] = b[j], j++;

    while(i <= n)
        c[++k] = a[i], i++;

    while(j <= m)
        c[++k] = b[j], j++;

    for(int i = 1; i <= k; ++i){
        cout << c[i] << " ";
        if(i % 10 == 0)
            cout << endl;
    }

    return 0;
}
Comentarii

S-ar putea sa iti placa