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 kminsum.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 kminsum.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 ≤ n, m ≤ 1000
*1 ≤ k ≤ 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 ==
;Intrare
:5 3 4
:1 2 3 4 5
:2 3 6
;Iesire
;Datele introduse corespund restrictiilor impuse
:1 2
:1 3
:2 2
:2 3

== Exemplul 2 ==
;Intrare
:5 3 4
:1 4 2 9 5
:2 3 6
;Iesire
;Datele introduse nu corespund restrictiilor impuse


== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def k_min_sum(n, m, k, A, B):
    pairs = []
    
    for i in range(min(k, n)):
        for j in range(min(k, m)):
            pairs.append((A[i], B[j]))

    pairs.sort(key=lambda x: sum(x))
    
    return pairs[:k]

def main():
    with open("kminsum.txt", "r") as file:
        n, m, k = map(int, file.readline().split())
        A = list(map(int, file.readline().split()))
        B = list(map(int, file.readline().split()))

    result = k_min_sum(n, m, k, A, B)

    with open("kminsum.txt", "w") as file_out:
        for pair in result:
            file_out.write(f"{pair[0]} {pair[1]}\n")

if __name__ == "__main__":
    main()

</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.