#184Programare

Intercalarea unei mulțimi între două elemente consecutive ale alteia

Enunț

Se citesc de la tastatură m și n și apoi un șir de m numere reprezentând elementele mulțimii A și n numere reprezentând elementele mulțimii B, toate numerele fiind numere naturale de cel mult patru cifre și ambele mulțimi fiind sortate crescător.

Se cere să se intercaleze elementele mulțimii B între două elemente consecutive din mulțimea A, dacă acest lucru este posibil. Se va afișa mulțimea astfel formată. Dacă nu este posibil, se va afișa mesajul IMPOSIBIL.

Pentru m = 7, n = 6, A = {3, 4, 5, 22, 29, 30, 33} și B = {7, 8, 11, 12, 13, 18} se va afișa:

3 4 5 7 8 11 12 13 18 22 29 30 33

Pentru m = 7, n = 6, A = {3, 4, 5, 22, 29, 30, 33} și B = {7, 8, 11, 12, 23, 28} se va afișa:

IMPOSIBIL

Rezolvare

C++

#include <iostream>
using namespace std;

int a[10005], b[10005];

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

    int k = -1;                             // pozitia dupa care se insereaza B
    for (int i = 0; i + 1 < m; i++)
        if (a[i] < b[0] && b[n - 1] < a[i + 1]) { k = i; break; }

    if (k == -1) { cout << "IMPOSIBIL\n"; return 0; }

    for (int i = 0; i <= k; i++)     cout << a[i] << " ";
    for (int i = 0; i < n; i++)      cout << b[i] << " ";
    for (int i = k + 1; i < m; i++)  cout << a[i] << " ";
    cout << "\n";
    return 0;
}

Cum funcționează

Enunțul e scurt, dar ascunde cerința reală. Nu se cere interclasarea celor două mulțimi (adică îmbinarea lor element cu element, cum se face la interclasarea a doi vectori sortați). Se cere ca tot blocul B să încapă între două elemente vecine din A.

Citește al doilea exemplu ca să te convingi: B = {7, 8, 11, 12, 23, 28} conține valori și sub 22, și peste 22, deci nu există nicio pereche de vecini din A care să-l cuprindă întreg. Răspunsul e IMPOSIBIL, deși o interclasare obișnuită ar fi funcționat perfect. Dacă ai fi interclasat, ai fi picat exact pe al doilea exemplu — de aceea se citesc ambele înainte de a scrie cod.

Ambele mulțimi fiind deja sortate crescător, condiția se reduce la capetele lui B:

a[i] < b[0]           si           b[n-1] < a[i+1]
   ^ tot B e peste vecinul din stanga    ^ tot B e sub vecinul din dreapta

Nu e nevoie să verifici fiecare element din B — dacă cel mai mic depășește a[i] și cel mai mare rămâne sub a[i+1], toate cele dintre ele sunt automat în interval. Asta e singura consecință practică a faptului că mulțimile sunt sortate, dar scurtează rezolvarea la câteva linii.

Bucla merge până la i + 1 < m, pentru că se compară perechi de vecini: ultimul i valid e m - 2. Enunțul cere inserarea între două elemente consecutive, deci pozițiile de la capete — înaintea lui a[0] sau după a[m-1] — nu sunt acceptate.

break oprește la prima poziție găsită. Cum A e sortată strict, nu poate exista decât una.

Greșeli frecvente

Interclasarea celor doi vectori — cea mai frecventă interpretare greșită. Trece pe primul exemplu și cade pe al doilea, unde ar trebui să afișeze IMPOSIBIL.
i + 1 <= m în condiția buclei — se citește a[m], în afara vectorului.
<= în loc de < — dacă b[0] e egal cu a[i], valoarea apare de două ori într-o mulțime, ceea ce contrazice enunțul.
Verificarea tuturor elementelor din B — corectă, dar inutilă; și, mai ales, semn că n-ai observat că mulțimile sunt sortate.
Uitarea cazului IMPOSIBIL — jumătate din punctaj stă în al doilea exemplu.

Apariții

Galati 2026 — problema 24 · sursa oficială