0250 - Interclasare 1

Cerinţa

Se dau două şiruri a şi b, cu n, respectiv m elemente, numere naturale, ordonate strict crescător. Să se afişeze, în ordine strict crescătoare, valorile existente în cel puţin unul dintre cele două şiruri. În cazul în care o valoare apare în ambele şiruri, va fi afişată o singură dată.

Date de intrare

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

Date de ieșire

Fişierul de ieşire interclasare1.out va conţine, în ordine strict crescătoare, valorile existente în cel puţin unul dintre cele două şiruri. Aceste valori vor fi afişate câte 10 pe o linie, separate prin spaţii. Ultima linie poate conţine mai puţin de 10 de 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

Exemplul 1

interclasare1.in

7

1 3 4

7 20 24 60

9

3 5 7

8 9 10 12

20 24

interclasare1.out

1 3 4 5 7 8 9 10 12 20

24 60

Exemplu 2

interclasare1.in

0

3 5 7

8 9 10 12

20 24

interclasare1.out

Datele de intrare nu corespund restricțiilor impuse.

Rezolvare

def interclasare_siruri(a, b):
    result = []
    i = 0
    j = 0

    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            result.append(a[i])
            i += 1
        elif a[i] > b[j]:
            result.append(b[j])
            j += 1
        else:
            result.append(a[i])
            i += 1
            j += 1

    while i < len(a):
        result.append(a[i])
        i += 1

    while j < len(b):
        result.append(b[j])
        j += 1

    return result


def citeste_sir(fisier):
    try:
        n = int(fisier.readline())
        if not (1 <= n <= 100000):
            raise ValueError("Datele de intrare nu corespund cerințelor impuse.")

        sir = []

        for _ in range(n):
            linie = fisier.readline().strip().split()
            sir.extend(map(int, linie))

        return sir
    except ValueError as e:
        print(f"Eroare: {e}")
        return None


def scrie_sir(fisier, sir):
    for i in range(0, len(sir), 10):
        fisier.write(" ".join(map(str, sir[i:i + 10])) + "\n")


if __name__ == "__main__":
    try:
        with open("interclasare1.in", "r") as input_file:
            a = citeste_sir(input_file)
            if a is None:
                exit()

            m = int(input_file.readline())
            if not (1 <= m <= 100000):
                raise ValueError("Datele de intrare nu corespund cerințelor impuse.")

            b = citeste_sir(input_file)
            if b is None:
                exit()

        interclasat = interclasare_siruri(a, b)

        with open("interclasare1.out", "w") as output_file:
            scrie_sir(output_file, interclasat)
    except Exception as e:
        print(f"Eroare generală: {e}")