Editing 2087 - K Min Sum

== Cerinta ==

Se consideră un număr natural '''k''' și două tablouri unidimensionale '''A și B''', cu '''n''' respectiv '''m''' elemente, numere întregi, sortate crescător. Să se afișeze primele '''k''' perechi de numere de sumă minimă. Fiecare pereche conține un număr din '''A''', un număr din '''B'''.

== Date de intrare ==

Fișierul de intrare '''kminsumin.txt''' conține pe prima linie trei numere naturale '''n, m și k''' având semnificația din enunț.
Pe a doua linie se găsesc '''n''' numere naturale separate prin spații ce reprezintă elementele tabloului '''A'''.
Pe a treia linie se găsesc '''m''' numere naturale separate prin spații ce reprezintă elementele tabloului '''B'''.

== Date de iesire ==

Fișierul de ieșire '''kminsumout.txt''' va conține '''k'' linii. Fiecare linie conține două numere întregi separate prin spațiu ce reprezintă descrierea unei perechi (un număr din A, un număr din B).

== Restrictii si precizari ==

*1 &les; n, m &les; 1000
*1 &les; k &les; 20000
*valorile elementelor celor două tablouri vor aparține intervalului '''[-1.000.000,1.000.000]'''
*ordinea de afișare a celor k perechi nu contează

== Exemplul 1 ==
;kminsumin.txt
:5 3 4
:1 2 3 4 5
:2 3 6
;kminsumout.txt
:Datele introduse corespund restrictiilor impuse
:1 2
:1 3
:2 2
:2 3

== Exemplul 2 ==
;kminsumin.txt
:5 3 4
:1 4 2 9 5
:2 3 6

:Datele introduse nu corespund restrictiilor impuse


== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_date_intrare(n, m, k, A, B):
    if not (1 <= n <= 1000 and 1 <= m <= 1000 and 1 <= k <= 20000):
        return False

    if not (-1000000 <= min(A + B) <= max(A + B) <= 1000000):
        return False

    return True

def k_min_sum_pairs(n, m, k, A, B):
    pairs = []

    i, j = 0, 0
    while i < n and j < m and len(pairs) < k:
        pairs.append((A[i], B[j]))
        if i + 1 < n and (j + 1 >= m or A[i + 1] + B[j] < A[i] + B[j + 1]):
            i += 1
        else:
            j += 1

    return pairs

# Citire date de intrare
try:
    with open("kminsumin.txt", "r") as f:
        n, m, k = map(int, f.readline().split())
        A = list(map(int, f.readline().split()))
        B = list(map(int, f.readline().split()))

    # Verificare date de intrare
    if not verifica_date_intrare(n, m, k, A, B):
        raise ValueError("Datele introduse nu corespund restricțiilor impuse.")

    # Calculare și afișare rezultat
    rezultat = k_min_sum_pairs(n, m, k, A, B)
    with open("kminsumout.txt", "w") as g:
        for pair in rezultat:
            g.write(f"{pair[0]} {pair[1]}\n")

except ValueError as ve:
    print(ve)


</syntaxhighlight>

== Explicatie ==

Tablou A conține 5 numere sortate crescător, tablou B conține 3 numere sortate crescător. Se pot forma 5•3 perechi. Primele 4 perechi corect formate de sumă minimă sunt: 1 2, 1 3, 2 2, 2 3.