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.