2252 - Profu - Revision history

Ramona Dragoș: /* Exemplu 2 */

2024-01-05T13:15:23Z

Exemplu 2

← Older revision		Revision as of 13:15, 5 January 2024
Line 24:		Line 24:
	: 0		: 0
	; '''profuout.txt'''		; '''profuout.txt'''
	: ~~Datele~~ nu ~~corespund restrictiilor~~		: DNumarul nu respecta restrictiile.
	<br>		<br>

	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>

Ramona Dragoș at 13:14, 5 January 2024

2024-01-05T13:14:38Z

← Older revision		Revision as of 13:14, 5 January 2024
Line 2:		Line 2:
	Alex este un copil destul de bun la informatica însă are un defect: Poate fi foarte enervant(prin enervant se înțelege ca își stresează profesorii cu mesaje pe Messenger). Profesorul de informatica s-a săturat de această situație așa ca i-a spus lui Alex ca dacă nu rezolvă următoarea problema îl va bloca pe Messenger. Alex nu vrea sa se întâmple acest lucru deoarece așa e conștient ca nu va mai avea pe cine stresa. Problema sună așa:		Alex este un copil destul de bun la informatica însă are un defect: Poate fi foarte enervant(prin enervant se înțelege ca își stresează profesorii cu mesaje pe Messenger). Profesorul de informatica s-a săturat de această situație așa ca i-a spus lui Alex ca dacă nu rezolvă următoarea problema îl va bloca pe Messenger. Alex nu vrea sa se întâmple acest lucru deoarece așa e conștient ca nu va mai avea pe cine stresa. Problema sună așa:

	Avem n cutii așezate într-o stivă astfel încât avem acces doar la prima cutie.Pentru fiecare cutie sa știe un număr A[i] reprezentând volumul cutiei i = 1,2...,n. Aceste cutii trebuie transportate din localitatea A în localitatea B știind ca se pot efectua maxim k transporturi (în cazul în care s-ar efectua mai multe mașina ar rămâne fără combustibil) și de asemenea fiind o mașina închiriată trebuie sa aibă capacitatea minimă x necesară pentru a efectua cele k transporturi. Numărul x este cel ce îi dă bătăi de cap lui Alex așa ca el vă roagă să îl ajutați!		Avem '''n''' cutii așezate într-o stivă astfel încât avem acces doar la prima cutie.Pentru fiecare cutie sa știe un număr '''A[i]''' reprezentând volumul cutiei '''i = 1,2...,n'''. Aceste cutii trebuie transportate din localitatea A în localitatea B știind ca se pot efectua maxim '''k''' transporturi (în cazul în care s-ar efectua mai multe mașina ar rămâne fără combustibil) și de asemenea fiind o mașina închiriată trebuie sa aibă capacitatea minimă '''x''' necesară pentru a efectua cele '''k''' transporturi. Numărul '''x''' este cel ce îi dă bătăi de cap lui Alex așa ca el vă roagă să îl ajutați!
	== Date de intrare ==		== Date de intrare ==
	Pe prima linie a fișierului profuin.txt se vor găsi cele doua numere n și k cu semnificația din enunț apoi pe a doua linie a fișierului se vor găsi n numere naturale.		Pe prima linie a fișierului '''profuin.txt''' se vor găsi cele doua numere '''n''' și '''k''' cu semnificația din enunț apoi pe a doua linie a fișierului se vor găsi '''n''' numere naturale.
	== Date de ieșire ==		== Date de ieșire ==
	Fișierul de ieșire profuout.txt va conține pe prima linie numărul x, reprezentând capacitatea minima a mașini ce trebuie închiriată.		Fișierul de ieșire '''profuout.txt''' va conține pe prima linie numărul '''x''', reprezentând capacitatea minima a mașini ce trebuie închiriată.
	== Restricții și precizări ==		== Restricții și precizări ==
	*1 &les; n &les; 500.000		*'''1 &les; n &les; 500.000'''
	*numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000		*numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât '''1.000.000'''
	== Exemplu 1 ==		== Exemplu 1 ==
	; profuin.txt		; '''profuin.txt'''
	:6 3		:6 3
	:7 3 2 3 1 4		:7 3 2 3 1 4
	;profuout.txt		; '''profuout.txt'''
	:8		:8
	<br>		<br>
	== Explicatie ==		== Explicatie ==
	La primul transport este încărcată prima saltea (care are volumul 7). La cel de-al doilea transport sunt încărcate saltele 2 și 3 (volumul total este 3 + 2 = 5). La cel de-al treilea transport sunt încărcate saltele 4, 5 și 6 (volumul total este 3 + 1 + 4 = 8 fiind cel mai mic rezultat posibil)		La primul transport este încărcată prima saltea (care are volumul '''7'''). La cel de-al doilea transport sunt încărcate saltele '''2''' și '''3''' (volumul total este '''3 + 2 = 5'''). La cel de-al treilea transport sunt încărcate saltele '''4''', '''5''' și '''6''' (volumul total este '''3 + 1 + 4 = 8''' fiind cel mai mic rezultat posibil)
	== Exemplu 2 ==		== Exemplu 2 ==
	; profuin.txt		; '''profuin.txt'''
	: 0		: 0
	; profuout.txt		: 0
			; '''profuout.txt'''
	: Datele nu corespund restrictiilor		: Datele nu corespund restrictiilor
	<br>		<br>
Line 28:		Line 29:
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
	#2252 - Profu		#2252 - Profu
	def ~~check_restrictions~~(n, k, volumes):		def capacitate_minima(n, k, volumes):
	~~if not (1 <= n <= 500000):~~
	~~return False~~

	~~if not all(0 < volume < 1000000 for volume in volumes):~~
	~~return False~~

	~~return True~~

	~~def transport_capacity(n, k, volumes):~~
	~~if not check_restrictions(n, k, volumes):~~
	~~print("Datele nu corespund restrictiilor")~~
	~~return None~~

	~~volumes.sort(reverse=True)~~

	left, right = max(volumes), sum(volumes)		left, right = max(volumes), sum(volumes)

	while left < right:		while left < right:
	mid = (left + right) // 2		mid = (left + right) // 2
	~~required_transports = 1~~		transports, current_sum = 0, 0
	~~current_capacity~~ = 0

	for volume in volumes:		for volume in volumes:
	if ~~current_capacity~~ + volume > mid:		if current_sum + volume > mid:
	~~required_transports~~ += 1		transports += 1
	~~current_capacity~~ = 0		current_sum = 0

	~~current_capacity~~ += volume		current_sum += volume

	if ~~required_transports <~~= k:		transports += 1 # pentru ultimul transport
			if transports > k:
			left = mid + 1
			else:
	right = mid		right = mid
	~~else:~~
	~~left = mid + 1~~

	return left		return left

	~~# Citire date de intrare~~
	try:		try:
	with open("profuin.txt", "r") as ~~file~~:		# Citirea datelor de intrare
	n, k = map(int, ~~file~~.readline().split())		with open('profuin.txt', 'r') as f:
	volumes = list(map(int, ~~file~~.readline().split()))		n, k = map(int, f.readline().split())
	~~except FileNotFoundError:~~		volumes = list(map(int, f.readline().split()))
	~~print("Fisierul de intrare nu exista!")~~
	~~exit(~~)

	# ~~Calcul și scriere rezultat în fișierul~~ de ~~ieșire~~		# Calculul capacitatii minime si scrierea rezultatului in fisierul de iesire
	result = ~~transport_capacity~~(n, k, volumes)		result = capacitate_minima(n, k, volumes)
	~~if result is not None:~~		with open('profuout.txt', 'w') as g:
	with open("profuout.txt", "w") as ~~file~~:		g.write(str(result))
	~~file~~.write(str(result) ~~+ "\n"~~)		except Exception as e:
			# În caz de eroare, afișăm un mesaj corespunzător
			with open('profuout.txt', 'w') as f:
			f.write('Numarul nu respecta restrictiile.')

	</syntaxhighlight>		</syntaxhighlight>

Ramona Dragoș: Pagină nouă: == Cerința == Alex este un copil destul de bun la informatica însă are un defect: Poate fi foarte enervant(prin enervant se înțelege ca își stresează profesorii cu mesaje pe Messenger). Profesorul de informatica s-a săturat de această situație așa ca i-a spus lui Alex ca dacă nu rezolvă următoarea problema îl va bloca pe Messenger. Alex nu vrea sa se întâmple acest lucru deoarece așa e conștient ca nu va mai avea pe cine stresa. Problema sună așa: Avem...

2023-12-12T13:13:07Z

Pagină nouă: == Cerința == Alex este un copil destul de bun la informatica însă are un defect: Poate fi foarte enervant(prin enervant se înțelege ca își stresează profesorii cu mesaje pe Messenger). Profesorul de informatica s-a săturat de această situație așa ca i-a spus lui Alex ca dacă nu rezolvă următoarea problema îl va bloca pe Messenger. Alex nu vrea sa se întâmple acest lucru deoarece așa e conștient ca nu va mai avea pe cine stresa. Problema sună așa: Avem...

New page

== Cerința ==
Alex este un copil destul de bun la informatica însă are un defect: Poate fi foarte enervant(prin enervant se înțelege ca își stresează profesorii cu mesaje pe Messenger). Profesorul de informatica s-a săturat de această situație așa ca i-a spus lui Alex ca dacă nu rezolvă următoarea problema îl va bloca pe Messenger. Alex nu vrea sa se întâmple acest lucru deoarece așa e conștient ca nu va mai avea pe cine stresa. Problema sună așa:

Avem n cutii așezate într-o stivă astfel încât avem acces doar la prima cutie.Pentru fiecare cutie sa știe un număr A[i] reprezentând volumul cutiei i = 1,2...,n. Aceste cutii trebuie transportate din localitatea A în localitatea B știind ca se pot efectua maxim k transporturi (în cazul în care s-ar efectua mai multe mașina ar rămâne fără combustibil) și de asemenea fiind o mașina închiriată trebuie sa aibă capacitatea minimă x necesară pentru a efectua cele k transporturi. Numărul x este cel ce îi dă bătăi de cap lui Alex așa ca el vă roagă să îl ajutați!
== Date de intrare ==
Pe prima linie a fișierului profuin.txt se vor găsi cele doua numere n și k cu semnificația din enunț apoi pe a doua linie a fișierului se vor găsi n numere naturale.
== Date de ieșire ==
Fișierul de ieșire profuout.txt va conține pe prima linie numărul x, reprezentând capacitatea minima a mașini ce trebuie închiriată.
== Restricții și precizări ==
*1 &les; n &les; 500.000
*numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000
== Exemplu 1 ==
; profuin.txt
:6 3
:7 3 2 3 1 4
;profuout.txt
:8
<br>
== Explicatie ==
La primul transport este încărcată prima saltea (care are volumul 7). La cel de-al doilea transport sunt încărcate saltele 2 și 3 (volumul total este 3 + 2 = 5). La cel de-al treilea transport sunt încărcate saltele 4, 5 și 6 (volumul total este 3 + 1 + 4 = 8 fiind cel mai mic rezultat posibil)
== Exemplu 2 ==
; profuin.txt
: 0
; profuout.txt
: Datele nu corespund restrictiilor
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#2252 - Profu
def check_restrictions(n, k, volumes):
if not (1 <= n <= 500000):
return False

if not all(0 < volume < 1000000 for volume in volumes):
return False

return True

def transport_capacity(n, k, volumes):
if not check_restrictions(n, k, volumes):
print("Datele nu corespund restrictiilor")
return None

volumes.sort(reverse=True)

left, right = max(volumes), sum(volumes)

while left < right:
mid = (left + right) // 2
required_transports = 1
current_capacity = 0

for volume in volumes:
if current_capacity + volume > mid:
required_transports += 1
current_capacity = 0

current_capacity += volume

if required_transports <= k:
right = mid
else:
left = mid + 1

return left

# Citire date de intrare
try:
with open("profuin.txt", "r") as file:
n, k = map(int, file.readline().split())
volumes = list(map(int, file.readline().split()))
except FileNotFoundError:
print("Fisierul de intrare nu exista!")
exit()

# Calcul și scriere rezultat în fișierul de ieșire
result = transport_capacity(n, k, volumes)
if result is not None:
with open("profuout.txt", "w") as file:
file.write(str(result) + "\n")

</syntaxhighlight>