Benzar Ioan at 23:56, 2 June 2024

2024-06-02T23:56:32Z

← Older revision		Revision as of 23:56, 2 June 2024
Line 1:		Line 1:
	== Cerința ==		== Cerința ==
	~~Într-~~o ~~cafenea~~, ~~un barista~~ trebuie să ~~pregătească diverse tipuri~~ de cafea ~~pentru clienți~~. Fiecare ~~comandă~~ de cafea ~~are~~ un ~~anumit timp~~ de ~~preparare~~, ~~iar barista dorește să minimizeze timpul total~~ de ~~așteptare al clienților~~. ~~Sarcina ta este~~ să ~~implementezi~~ un program care ~~să determine ordinea optimă în care barista trebuie să prepare comenzile pentru a minimiza timpul total de așteptare utilizând o metodă greedy~~.		Algorel a primit de la părinţi o sumă de bani, S, şi o plasă în care încap K grame de cafea. Algorel trebuie să meargă la piaţă şi să cumpere suficientă cafea încât să umple plasa. Pe de altă parte, părinţii nu îi cer înapoi restul. Dacă va reuşi să umple plasa, va putea păstra diferenţa de bani dintre suma primită S şi costul total al cafelei achiziţionate. Dacă nu va reuşi să umple plasa, atunci nu va rămâne cu niciun ban.

			La piaţă există N comercianţi care vând cafea. Fiecare dintre aceştia are o cantitate de Ci grame de cafea pe care o vinde cu preţul total de Pi lei (1 ≤ i ≤ N). Comercianţii nu au monede mai mici de 1 leu, aşa că, în cazul în care clientul cumpără o cantitate de cafea al cărei preţ nu este un număr întreg, acesta va plăti suma rotunjită la cea mai apropiată valoare întreagă mai mare sau egală cu valoarea datorată. De exemplu, dacă un comerciant vinde 1000 de grame de cafea la preţul de 25 de lei şi un client vrea să cumpere 250 de grame, atunci acesta va plăti 7 lei, deşi suma datorată era de 6.25 lei.
			Ajutaţi-l pe Algorel să rămână cu o sumă cât mai mare de bani, scriind un program care face acest calcul pe baza datelor corespunzătoare comercianţilor.
	== Date de intrare ==		== Date de intrare ==
	~~Programul citește~~ de la ~~tastatură~~:		Fişierul de intrare cafea.in va conţine pe prima linie, separate prin câte un spaţiu numerele naturale K, S şi N corespunzătoare capacităţii plasei, sumei pe pare o primeşte de la părinţi şi numărului de vânzători. Pe următoarele N linii se vor afla datele corespunzătoare comercianţilor: pe linia i + 1 se vor afla numerele naturale Ci şi Pi reprezentând cantitatea maximă de cafea pe care o vinde comerciantul numărul i şi preţul total cerut de acesta.

	~~Un număr întreg n~~ reprezentând numărul de ~~comenzi.~~
	~~O listă de n numere întregi reprezentând timpul de preparare pentru fiecare comandă~~.
	== Date de ieșire ==		== Date de ieșire ==
	~~Pe ecran se~~ va ~~afișa timpul total minim de așteptare al clienților~~.		Fișierul de ieșire cafea.out va conține pe prima linie un număr natural, reprezentând suma maximă care îi rămâne lui Algorel după ce umple plasa cu cafea.
	== Restricții și precizări ==		== Restricții și precizări ==
	*1 ~~&les; '''n''' &les;~~ 100		*1 ≤ K ≤ 1 000 000 000
	* ~~Timpul de preparare~~ pentru ~~fiecare comandă este un număr întreg pozitiv~~		*1 ≤ S ≤ 1 000 000 000
			*1 ≤ N ≤ 100 000
			*Ci ∈ [1, 100 000], pentru 1 ≤ i ≤ N
			*Pi ∈ [1, 100 000], pentru 1 ≤ i ≤ N

	== Exemplu 1 ==		== Exemplu 1 ==
	;Intrare		;Intrare
	4<br>		1000 200 4<br>
	~~3 1 4 3~~		500 85<br>
			600 45<br>
	~~;Iesire~~		250 35<br>
	23		1000 1000
	~~== Exemplu 2 ==~~
	~~;Intrare~~
	3<br>
	~~2 5 1~~

	;Iesire		;Iesire
	12		94

	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
	def ~~citeste_date~~():		def main():
	~~try~~:		with open("cafea.in", "r") as f:
	n = int(~~input~~(~~"Introduceți numărul de comenzi~~ (~~n): "~~))		k, s, n = map(int, f.readline().strip().split())
	~~timpuri~~ = ~~list~~(map(int, ~~input~~(~~"Introduceți timpii de preparare, separați prin spațiu: "~~).split()))		comercianti = []
	~~return n~~, ~~timpuri~~		for _ in range(n):
	~~except ValueError:~~		ci, pi = map(int, f.readline().strip().split())
	~~return None~~, ~~None~~		comercianti.append((pi / ci, ci, pi)) # (preț per gram, cantitate maximă, preț total)

	~~def valideaza_date(n, timpuri):~~		# Sortăm comercianții după prețul per gram
	~~if not (1 <= n <= 100):~~		comercianti.sort()
	~~return False~~
	~~if len(timpuri) != n:~~
	~~return False~~
	~~if not all(isinstance~~(~~timp, int) and timp > 0 for timp in timpuri~~):
	~~return False~~
	~~return True~~

	~~def calculeaza_timp_minim_asteptare(n, timpuri):~~		cantitate_cumparata = 0
	~~timpuri.sort()~~		cost_total = 0
	~~timp_asteptare_total~~ = 0
	~~timp_cumulat~~ = 0

	for ~~timp~~ in ~~timpuri~~:		for pret_per_gram, cantitate_max, pret_total in comercianti:
	~~timp_cumulat~~ += ~~timp~~		if cantitate_cumparata + cantitate_max <= k:
	~~timp_asteptare_total~~ += ~~timp_cumulat~~		cantitate_cumparata += cantitate_max
			cost_total += pret_total
			else:
			cantitate_necesara = k - cantitate_cumparata
			cost_total += cantitate_necesara * pret_per_gram
			cantitate_cumparata += cantitate_necesara
			break

	~~return timp_asteptare_total~~		bani_ramasi = s - cost_total

	~~def main():~~		with open("cafea.out", "w") as f:
	~~n, timpuri = citeste_date~~()		f.write(f"{int(bani_ramasi)}\n")

	~~if n is None or timpuri is None or not valideaza_date(n~~, ~~timpuri~~):
	~~print~~("~~Datele de intrare nu corespund restricțiilor impuse.")~~
	~~return~~

	~~print~~(~~"Datele de intrare corespund restricțiilor impuse."~~)
	~~timp_minim_asteptare = calculeaza_timp_minim_asteptare(~~n~~, timpuri)~~
	~~print(timp_minim_asteptare~~)

	if __name__ == "__main__":		if __name__ == "__main__":
	main()		main()


	</syntaxhighlight>		</syntaxhighlight>

Benzar Ioan: Pagină nouă: == Cerința == Într-o cafenea, un barista trebuie să pregătească diverse tipuri de cafea pentru clienți. Fiecare comandă de cafea are un anumit timp de preparare, iar barista dorește să minimizeze timpul total de așteptare al clienților. Sarcina ta este să implementezi un program care să determine ordinea optimă în care barista trebuie să prepare comenzile pentru a minimiza timpul total de așteptare utilizând o metodă greedy. == Date de intrare == Programul...

2024-06-02T18:57:35Z

Pagină nouă: == Cerința == Într-o cafenea, un barista trebuie să pregătească diverse tipuri de cafea pentru clienți. Fiecare comandă de cafea are un anumit timp de preparare, iar barista dorește să minimizeze timpul total de așteptare al clienților. Sarcina ta este să implementezi un program care să determine ordinea optimă în care barista trebuie să prepare comenzile pentru a minimiza timpul total de așteptare utilizând o metodă greedy. == Date de intrare == Programul...

New page

== Cerința ==
Într-o cafenea, un barista trebuie să pregătească diverse tipuri de cafea pentru clienți. Fiecare comandă de cafea are un anumit timp de preparare, iar barista dorește să minimizeze timpul total de așteptare al clienților. Sarcina ta este să implementezi un program care să determine ordinea optimă în care barista trebuie să prepare comenzile pentru a minimiza timpul total de așteptare utilizând o metodă greedy.
== Date de intrare ==
Programul citește de la tastatură:

Un număr întreg n reprezentând numărul de comenzi.
O listă de n numere întregi reprezentând timpul de preparare pentru fiecare comandă.
== Date de ieșire ==
Pe ecran se va afișa timpul total minim de așteptare al clienților.
== Restricții și precizări ==
*1 &les; '''n''' &les; 100
* Timpul de preparare pentru fiecare comandă este un număr întreg pozitiv

== Exemplu 1 ==
;Intrare
4<br>
3 1 4 3

;Iesire
23
== Exemplu 2 ==
;Intrare
3<br>
2 5 1

;Iesire
12

== Rezolvare ==
<syntaxhighlight lang="python" line>
def citeste_date():
try:
n = int(input("Introduceți numărul de comenzi (n): "))
timpuri = list(map(int, input("Introduceți timpii de preparare, separați prin spațiu: ").split()))
return n, timpuri
except ValueError:
return None, None

def valideaza_date(n, timpuri):
if not (1 <= n <= 100):
return False
if len(timpuri) != n:
return False
if not all(isinstance(timp, int) and timp > 0 for timp in timpuri):
return False
return True

def calculeaza_timp_minim_asteptare(n, timpuri):
timpuri.sort()
timp_asteptare_total = 0
timp_cumulat = 0

for timp in timpuri:
timp_cumulat += timp
timp_asteptare_total += timp_cumulat

return timp_asteptare_total

def main():
n, timpuri = citeste_date()

if n is None or timpuri is None or not valideaza_date(n, timpuri):
print("Datele de intrare nu corespund restricțiilor impuse.")
return

print("Datele de intrare corespund restricțiilor impuse.")
timp_minim_asteptare = calculeaza_timp_minim_asteptare(n, timpuri)
print(timp_minim_asteptare)

if __name__ == "__main__":
main()

</syntaxhighlight>

3739 - Cafea - Revision history

Benzar Ioan at 23:56, 2 June 2024