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 ⩽ 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

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

1. Citire date de intrare

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()))

1. Calculare si afisare rezultat

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

1. Scriere rezultat in fisierul de iesire

with open("kminsumout.txt", "w") as g:

   for pair in result:
       g.write(f"{pair[0]} {pair[1]}\n")

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