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

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