2087 - K Min Sum - Revision history

Mesarosdenisa: /* Rezolvare */

2023-12-29T12:01:28Z

Rezolvare

← Older revision		Revision as of 12:01, 29 December 2023
Line 43:		Line 43:
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python3" line="1">		<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):		def k_min_sum_pairs(n, m, k, A, B):
	pairs = []		pairs = []
Line 57:		Line 66:

	# Citire date de intrare		# Citire date de intrare
	with open("kminsumin.txt", "r") as f:		try:
	n, m, k = map(int, f.readline().split())		with open("kminsumin.txt", "r") as f:
	A = list(map(int, f.readline().split()))		n, m, k = map(int, f.readline().split())
	B = list(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")

	~~# Calculare si afisare rezultat~~		except ValueError as ve:
	~~result = k_min_sum_pairs~~(~~n, m, k, A, B~~)		print(ve)

	~~# 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>		</syntaxhighlight>

Mesarosdenisa: /* Rezolvare */

2023-12-27T10:38:03Z

Rezolvare

← Older revision		Revision as of 10:38, 27 December 2023
Line 43:		Line 43:
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python3" line="1">		<syntaxhighlight lang="python3" line="1">
	def ~~k_min_sum~~(n, m, k, A, B):		def k_min_sum_pairs(n, m, k, A, B):
	pairs = []		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))		i, j = 0, 0
			while i < n and j < m and len(pairs) < k:
	~~return 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

	~~def main():~~		return pairs
	~~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)		# 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()))

	~~with open("kminsum.txt", "w") as file_out:~~		# Calculare si afisare rezultat
	~~for pair in~~ result:		result = k_min_sum_pairs(n, m, k, A, B)
	~~file_out.write~~(~~f"{pair[0]} {pair[1]}\~~n")

	~~if __name__ ==~~ "~~__main__~~":		# Scriere rezultat in fisierul de iesire
	~~main~~()		with open("kminsumout.txt", "w") as g:
			for pair in result:
			g.write(f"{pair[0]} {pair[1]}\n")

	</syntaxhighlight>		</syntaxhighlight>

Mesarosdenisa at 10:35, 27 December 2023

2023-12-27T10:35:35Z

← Older revision		Revision as of 10:35, 27 December 2023
Line 1:		Line 1:
	== Cerinta ==		== 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.		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 ==		== 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ț.		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 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.		Pe a treia linie se găsesc '''m''' numere naturale separate prin spații ce reprezintă elementele tabloului '''B'''.

	== Date de iesire ==		== 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).		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 ==		== Restrictii si precizari ==

	*1 ≤ n, m ≤ 1000		*1 &les; n, m &les; 1000
	*1 ≤ k ≤ 20000		*1 &les; k &les; 20000
	*valorile elementelor celor două tablouri vor aparține intervalului [-1.000.000,1.000.000]		*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ă		*ordinea de afișare a celor k perechi nu contează

	== Exemplul 1 ==		== Exemplul 1 ==
	;~~Intrare~~		;kminsumin.txt
	:5 3 4		:5 3 4
	:1 2 3 4 5		:1 2 3 4 5
	:2 3 6		:2 3 6
	;~~Iesire~~		;kminsumout.txt
	;Datele introduse corespund restrictiilor impuse		:Datele introduse corespund restrictiilor impuse
	:1 2		:1 2
	:1 3		:1 3
Line 33:		Line 33:

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

Mesarosdenisa: Pagină nouă: == 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 pr...

2023-12-12T16:19:29Z

Pagină nouă: == 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 pr...

New page

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