3575 - Br - Revision history

Vardai Erwin at 13:04, 6 May 2023

2023-05-06T13:04:40Z

← Older revision		Revision as of 13:04, 6 May 2023
Line 61:		Line 61:
	:3		:3
	:4		:4
	:0		:1
	:5		:5

Line 97:		Line 97:
	if x < 1 or x > 3000000:		if x < 1 or x > 3000000:
	raise ValueError("Invalid amount of money")		raise ValueError("Invalid amount of money")


	def calculate_round_buying(n, c_values, k, x):		def calculate_round_buying(n, c_values, k, x):
Line 103:		Line 103:
	max_beers_bought = 0		max_beers_bought = 0
	total_cost = 0		total_cost = 0

	for i in range(n):		for i in range(n):
	j = (k + i - 1) % n		j = (k + i - 1) % n
Line 112:		Line 112:
	else:		else:
	break		break

	if total_cost < x:		if total_cost < x:
	for i in range(n):		for i in range(n):
Line 122:		Line 122:
	if total_cost == x:		if total_cost == x:
	break		break

	return max_beers_bought		return max_beers_bought


	~~def main()~~:		if __name__ == "__main__":
	try:		try:
	with open("br.in") as f:		with open("br.in") as f:
Line 132:		Line 131:
	c_values = list(map(int, f.readline().split()))		c_values = list(map(int, f.readline().split()))
	rounds = [tuple(map(int, line.split())) for line in f]		rounds = [tuple(map(int, line.split())) for line in f]
			print("Datele introduse corespund restricțiilor impuse.")
	validate_input(n, t, c_values, rounds)		validate_input(n, t, c_values, rounds)

	with open("br.out", "w") as f:		with open("br.out", "w") as f:
	for k, x in rounds:		for k, x in rounds:
	f.write(str(calculate_round_buying(n, c_values, k, x)) + "\n")		f.write(str(calculate_round_buying(n, c_values, k, x)) + "\n")
	except Exception as e:		except Exception as e:
	print("~~An error occurred:~~"~~, e~~)		print("Datele introduse nu corespund restricțiilor impuse.")


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



	</syntaxhighlight>		</syntaxhighlight>

Cuceu Andrei at 15:07, 30 April 2023

2023-04-30T15:07:45Z

@@ Line 82: / Line 82: @@
 <syntaxhighlight lang="python" line="1" start="1">
-if __name__ == '__main__':
+def validate_input(n, t, c_values, rounds):
-     # citire date de intrare
+    if n < 1 or n > 15000:
-     with open('br.in', 'r') as f:
+        raise ValueError("Invalid number of friends")
-        n, t = map(int, f.readline().split())
+    if t < 1 or t > 10000:
-        costuri = list(map(int, f.readline().split()))
+        raise ValueError("Invalid number of rounds")
-        for _ in range(t):
+    if len(c_values) != n:
-             k, x = map(int, f.readline().split())
+        raise ValueError("Invalid number of beer costs")
-            # apelare functie si afisare rezultat
+    if any(ci < 1 or ci > 100 for ci in c_values):
-            print(numar_maxim_beri(costuri, x, k-1))
+        raise ValueError("Invalid beer cost")
 </syntaxhighlight>

Vardai Erwin: /* Exemplul 1 */

2023-04-22T18:52:50Z

Exemplul 1

← Older revision		Revision as of 18:52, 22 April 2023
Line 63:		Line 63:
	:0		:0
	:5		:5

			;Ieșire
			:Datele de intrare corespund restricțiilor impuse.

	==Explicatie==		==Explicatie==

Vardai Erwin: /* Date de ieșire */

2023-04-22T18:52:25Z

Date de ieșire

← Older revision		Revision as of 18:52, 22 April 2023
Line 29:		Line 29:
	==Date de ieșire==		==Date de ieșire==

			Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele de intrare corespund restricțiilor impuse."
	Fişierul de ieşire '''br.out''' va conţine '''T''' linii, fiecare cu un singur număr '''Di''' reprezentând numărul de beri pe care le va cumpăra prietenul '''ki''' cu suma de bani '''xi''' in condiţiile problemei.		Fişierul de ieşire '''br.out''' va conţine '''T''' linii, fiecare cu un singur număr '''Di''' reprezentând numărul de beri pe care le va cumpăra prietenul '''ki''' cu suma de bani '''xi''' in condiţiile problemei.
			În caz contrar, se va afișa pe ecran: "Datele de intrare nu corespund restricțiilor impuse."

	==Restricții de precizări==		==Restricții de precizări==

Vardai Erwin: /* Enunt */

2023-03-27T12:13:51Z

Enunt

← Older revision		Revision as of 12:13, 27 March 2023
Line 1:		Line 1:
	==~~Enunt~~==		==Enunț==

	'''N''' prieteni, numerotaţi de la '''1''' la '''N''', beau bere fără alcool la o masă rotundă. Pentru fiecare prieten i se cunoaşte '''Ci'''costul berii lui preferate. Din când în când, câte un prieten, fie el '''k''', cumpără câte o bere pentru o secvenţă de prieteni aflaţi pe poziţii consecutive la masă, începand cu el, în sensul acelor de ceasornic. El este dispus să cheltuiască x bani şi doreşte să facă cinste la un număr maxim posibil de prieteni.		'''N''' prieteni, numerotaţi de la '''1''' la '''N''', beau bere fără alcool la o masă rotundă. Pentru fiecare prieten i se cunoaşte '''Ci'''costul berii lui preferate. Din când în când, câte un prieten, fie el '''k''', cumpără câte o bere pentru o secvenţă de prieteni aflaţi pe poziţii consecutive la masă, începand cu el, în sensul acelor de ceasornic. El este dispus să cheltuiască x bani şi doreşte să facă cinste la un număr maxim posibil de prieteni.


	==Cerință==		==Cerință==

Cuceu Andrei: Pagină nouă: ==Enunt== '''N''' prieteni, numerotaţi de la '''1''' la '''N''', beau bere fără alcool la o masă rotundă. Pentru fiecare prieten i se cunoaşte '''Ci'''costul berii lui preferate. Din când în când, câte un prieten, fie el '''k''', cumpără câte o bere pentru o secvenţă de prieteni aflaţi pe poziţii consecutive la masă, începand cu el, în sensul acelor de ceasornic. El este dispus să cheltuiască x bani şi doreşte să facă cinste la un număr maxim posib...

2023-03-25T11:00:46Z

Pagină nouă: ==Enunt== '''N''' prieteni, numerotaţi de la '''1''' la '''N''', beau bere fără alcool la o masă rotundă. Pentru fiecare prieten i se cunoaşte '''Ci'''costul berii lui preferate. Din când în când, câte un prieten, fie el '''k''', cumpără câte o bere pentru o secvenţă de prieteni aflaţi pe poziţii consecutive la masă, începand cu el, în sensul acelor de ceasornic. El este dispus să cheltuiască x bani şi doreşte să facă cinste la un număr maxim posib...

New page

==Enunt==

'''N''' prieteni, numerotaţi de la '''1''' la '''N''', beau bere fără alcool la o masă rotundă. Pentru fiecare prieten i se cunoaşte '''Ci'''costul berii lui preferate. Din când în când, câte un prieten, fie el '''k''', cumpără câte o bere pentru o secvenţă de prieteni aflaţi pe poziţii consecutive la masă, începand cu el, în sensul acelor de ceasornic. El este dispus să cheltuiască x bani şi doreşte să facă cinste la un număr maxim posibil de prieteni.

==Cerință==

Se cere numărul de beri pe care le va cumpăra fiecare prieten '''k''' în limita sumei '''x''' de bani de care dispune. În caz că '''x''' este mai mare decât costul berilor pentru toţi prietenii de la masă, se vor achiziţiona maxim '''N''' beri.

==Date de intrare==

Prima linie a fişierului de intrare '''br.in''' conţine două numere naturale '''N''' şi '''T''' separate printr-un spaţiu reprezentând numărul de prieteni şi respectiv numărul de prieteni care doresc să facă cinste prietenilor săi.
A doua linie a fişierului de intrare conţine '''N''' numere naturale '''C1,C2,…,CN'''
, separate prin câte un spaţiu, reprezentând costurile berilor preferate de fiecare prieten. Berea pentru prietenul '''i''' are costul '''Ci'''
.
Fiecare din următoarele T linii conţine câte două numere separate printr-un spaţiu:
;'''k1x1'''

;'''k2x2'''

;…
;'''kTxT'''

precizând indicele câte unui prieten care face cinste şi respectiv suma de bani de care acesta dispune.

==Date de ieșire==

Fişierul de ieşire '''br.out''' va conţine '''T''' linii, fiecare cu un singur număr '''Di''' reprezentând numărul de beri pe care le va cumpăra prietenul '''ki''' cu suma de bani '''xi''' in condiţiile problemei.

==Restricții de precizări==

*'''1 ≤ N ≤ 15.000'''
*'''1 ≤ T ≤ 10.000'''
*'''1≤Ci≤100'''
*'''1≤ki≤N'''
*'''1≤xi≤3.000.000'''
*Un program corect, care se încadrează în timp pentru '''T ≤ 4000''', va obţine cel puţin '''30''' de puncte
*Un program corect, care se încadrează în timp pentru '''N ≤ 2000''', va obţine cel puţin '''60''' de puncte
*Prietenii beau numai berea lor preferată.

==Exemplu==
===Exemplul 1===

; '''br.in'''

:5 4
:10 5 15 22 13
:1 32
:4 50
:1 9
:4 200

;'''br.out'''

:3
:4
:0
:5

==Explicatie==

Prietenul '''1''' cumpără câte o bere pentru el şi pentru prietenii '''2''', '''3'''. Costul celor '''3''' beri este '''30'''.
Prietenul '''4'''cumpără '''4''' beri: câte una pentru el şi pentru prietenii '''5''', '''1''', '''2'''. Costul celor '''4''' beri este '''50'''.
Cu '''9''' bani prietenul '''1''' nu poate cumpăra nici măcar berea lui.
Prietenul '''4''' cumpără '''5''' beri. Costul celor '''5''' beri este sub limita de cost '''200'''.

==Rezolvare==
===Rezolvare ver. 1===
<syntaxhighlight lang="python" line="1" start="1">

# functie care calculeaza numarul maxim de beri ce pot fi cumparate cu o anumita suma
def numar_maxim_beri(costuri, x, k):
n = len(costuri)
# daca x este mai mare decat costul tuturor berilor, se vor cumpara maxim N beri
if x >= sum(costuri):
return n
# initializare variabile
i = k
j = (k + 1) % n
cost_total = costuri[k]
numar_beri = 1
numar_maxim = 1
# algoritmul lui Kadane pentru secvente maxime de suma
while i != j:
# daca se depaseste suma x, se decrementeaza variabilele pana la atingerea sumei x
while cost_total + costuri[j] > x and i != j:
cost_total -= costuri[i]
numar_beri -= 1
i = (i + 1) % n
# se adauga costul berii si se incrementeaza numarul de beri
cost_total += costuri[j]
numar_beri += 1
j = (j + 1) % n
# se actualizeaza numarul maxim de beri si se pastreaza secventa maxima
if numar_beri > numar_maxim:
numar_maxim = numar_beri
return numar_maxim

if __name__ == '__main__':
# citire date de intrare
with open('br.in', 'r') as f:
n, t = map(int, f.readline().split())
costuri = list(map(int, f.readline().split()))
for _ in range(t):
k, x = map(int, f.readline().split())
# apelare functie si afisare rezultat
print(numar_maxim_beri(costuri, x, k-1))

</syntaxhighlight>