1248 - carti2 - Revision history

Monica Dragos: /* Date de ieșire */

2023-05-04T20:49:52Z

Date de ieșire

← Older revision		Revision as of 20:49, 4 May 2023
Line 11:		Line 11:
	==Date de ieșire==		==Date de ieșire==
	Fișierul de ieșire carti2.out va conține pe prima linie numerele a și b, reprezentând minim lexicografic al numerelor caselor pentru care numărul de cărți maxim este vândut.		Fișierul de ieșire carti2.out va conține pe prima linie numerele a și b, reprezentând minim lexicografic al numerelor caselor pentru care numărul de cărți maxim este vândut.
	În consolă se va afișa un mesaj de validare a datelor ("Input valid" ~~sau~~ ValueError cu un mesaj de corectare a datelor).		În acest caz, în consolă se va afișa un mesaj de validare a datelor "Input valid". În caz contrar, va apărea ValueError cu un mesaj de corectare a datelor.

	==Restricții și precizări==		==Restricții și precizări==
	* 1 ≤ n ≤ 100.000		* 1 ≤ n ≤ 100.000

Cata at 06:47, 3 May 2023

2023-05-03T06:47:31Z

← Older revision		Revision as of 06:47, 3 May 2023
Line 11:		Line 11:
	==Date de ieșire==		==Date de ieșire==
	Fișierul de ieșire carti2.out va conține pe prima linie numerele a și b, reprezentând minim lexicografic al numerelor caselor pentru care numărul de cărți maxim este vândut.		Fișierul de ieșire carti2.out va conține pe prima linie numerele a și b, reprezentând minim lexicografic al numerelor caselor pentru care numărul de cărți maxim este vândut.
	În consolă se va afișa un mesaj de validare a datelor.		În consolă se va afișa un mesaj de validare a datelor ("Input valid" sau ValueError cu un mesaj de corectare a datelor).
	==Restricții și precizări==		==Restricții și precizări==
	* 1 ≤ n ≤ 100.000		* 1 ≤ n ≤ 100.000
Line 23:		Line 23:
	: 2 4		: 2 4
	; Consolă		; Consolă
	: ~~Valid input~~		: Input valid
	==Explicație==		==Explicație==
	Intervalul [2, 4], deoarece 2 + 3 + 4 = 9		Intervalul [2, 4], deoarece 2 + 3 + 4 = 9
Line 38:		Line 38:
	def validate_input(n, x):		def validate_input(n, x):
	if not 1 <= n <= 100000:		if not 1 <= n <= 100000:
	raise ValueError("~~Invalid value for~~ n. ~~Must be between~~ 1 ~~and~~ 100000.")		raise ValueError("Valoare invalidă pentru n. Trebuie să fie între 1 și 100000.")
	if not 1 <= x <= 1000000000:		if not 1 <= x <= 1000000000:
	raise ValueError("~~Invalid value for~~ x. ~~Must be between~~ 1 ~~and~~ 1000000000.")		raise ValueError("Valoare invalidă pentru x. Trebuie să fie între 1 și 1000000000.")

	def read_input():		def read_input():
	n, x = map(int, input().split())		n, x = map(int, input().split())
	validate_input(n, x)		validate_input(n, x)
	print("~~Valid input~~")		print("Input valid")
	sp = [0] * (n + 1)		sp = [0] * (n + 1)
	for i in range(1, n + 1):		for i in range(1, n + 1):
Line 88:		Line 88:

	==Explicație cod==		==Explicație cod==
	~~Acesta este un program Python care primește date de intrare din fișierul~~ "~~carti2.in~~" și ~~scrie datele~~ de ~~ieșire în fișierul "carti2~~.~~out". În esență, programul primește un număr n și un număr x, reprezentând numărul de cărți și suma de bani disponibile~~, ~~respectiv, și~~ o ~~listă de prețuri pentru fiecare carte. Scopul programului~~ este ~~de a găsi o pereche de indici (st, dr) astfel încât suma prețurilor de cărți de la st la dr să fie maximă și~~ mai ~~mică sau egală cu x~~.		Acest cod începe prin importarea modulului "sys", care oferă funcții și variabile utilizate pentru a manipula funcționalitatea specifică a sistemului de operare. Apoi, se definește o valoare infinită numită "Inf" care este utilizată mai târziu în cod.

	~~Funcțiile definite în cod includ:~~		În continuare, fișierele de intrare și ieșire sunt deschise pentru citire și scriere, respectiv, utilizând metoda "open" a modulului "sys". Fișierul de intrare "carti2.in" va fi utilizat pentru citirea datelor de intrare, iar fișierul de ieșire "carti2.out" va fi utilizat pentru afișarea rezultatelor.

	validate_input~~: Această funcție verifică dacă valorile~~ n și x sunt ~~valide~~ și, ~~în caz contrar~~, ~~aruncă~~ o excepție.		Funcția "validate_input" primește doi parametri "n" și "x" și verifică dacă aceștia sunt în intervalul [1, 100000] și [1, 1000000000], respectiv. Dacă nu sunt, atunci se generează o excepție "ValueError" cu un mesaj corespunzător.
	read_input~~: Această funcție primește datele~~ de intrare și le ~~prelucrează pentru a crea~~ o listă sp care ~~reprezintă~~ suma ~~cumulată a prețurilor pentru~~ fiecare ~~carte, începând cu prima carte~~.
	CautBin: ~~Această funcție implementează~~ o ~~căutare binară pentru a găsi~~ poziția la care suma ~~prețurilor~~ de la poz până la ~~mijlocul intervalului este~~ mai ~~mare~~ sau egală cu x. ~~Această funcție este apelată~~ în ~~cadrul funcției find_books~~.		Funcția "read_input" citește valorile "n" și "x" de la intrare, le validează folosind funcția "validate_input", afișează un mesaj de "Input valid" și apoi citește "n" numere întregi de la intrare și le stochează într-o listă numită "sp". Lista "sp" este o listă de suma acumulată, care conține suma primelor "i" numere din intrare la fiecare poziție "i".
	find_books: Această funcție ~~parcurge lista sp și pentru fiecare index i~~ găsește ~~indexul j~~ astfel încât suma prețurilor ~~de cărți de la i la j este~~ maximă și mai mică sau egală cu x.
	Blocul principal ~~al programului apelează~~ funcțiile read_input și find_books, ~~apoi afișează indicii st~~ și ~~dr găsiți prin intermediul funcției find_books~~. Dacă valorile ~~pentru n sau x sunt nevalide, programul va afișa un mesaj de eroare~~.		Funcția "CautBin" primește patru parametri: valoarea "x" pe care o căutăm, poziția "poz" la care începem căutarea, numărul total de cărți "n" și lista "sp" cu suma acumulată. Această funcție caută poziția maximă "PozCautata" astfel încât suma acumulată de la poziția "poz" până la poziția "PozCautata" să fie mai mică sau egală cu "x". Căutarea se face utilizând o căutare binară, care reduce numărul de operații necesare în comparație cu o căutare liniară.

			Funcția "find_books" primește trei parametri: numărul total de cărți "n", valoarea maximă a sumei "x" și lista "sp" cu suma acumulată. Această funcție găsește cele mai multe cărți consecutive pe care le putem cumpăra, astfel încât suma totală a prețurilor lor să fie mai mică sau egală cu "x". Funcția utilizează funcția "CautBin" pentru a găsi poziția maximă "PozCautata" astfel încât suma acumulată să fie mai mică sau egală cu "x" și apoi compară această sumă cu maximul curent și, dacă este mai mare, actualizează valorile "maxim", "st" și "dr".

			Blocul `if __name__ == "__main__"` reprezintă o convenție folosită în Python pentru a verifica dacă scriptul curent este rulat ca program principal (adica rulat direct, nu importat ca modul în alt script).

			Dacă scriptul este rulat ca program principal, blocul de cod sub acest `if` va fi executat, altfel va fi ignorat. În acest caz, `try`/`except` blocul este folosit pentru a prinde orice excepții care pot fi ridicate în timpul rulării codului din funcțiile `read_input()` și `find_books()`.

			Astfel, dacă există excepții de tipul `ValueError` ridicate de funcția `validate_input()`, acestea vor fi prinse și mesajul de eroare corespunzător va fi afișat. Dacă nu apar erori, funcția `find_books()` este apelată și rezultatul acesteia (în acest caz, valorile `st` și `dr`) vor fi afișate la ieșirea standard.

Cata at 07:52, 28 April 2023

2023-04-28T07:52:15Z

← Older revision		Revision as of 07:52, 28 April 2023
Line 11:		Line 11:
	==Date de ieșire==		==Date de ieșire==
	Fișierul de ieșire carti2.out va conține pe prima linie numerele a și b, reprezentând minim lexicografic al numerelor caselor pentru care numărul de cărți maxim este vândut.		Fișierul de ieșire carti2.out va conține pe prima linie numerele a și b, reprezentând minim lexicografic al numerelor caselor pentru care numărul de cărți maxim este vândut.
			În consolă se va afișa un mesaj de validare a datelor.
	==Restricții și precizări==		==Restricții și precizări==
	* 1 ≤ n ≤ 100.000		* 1 ≤ n ≤ 100.000
Line 17:		Line 17:
	* 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==		==Exemplu==
	carti2.in		; carti2.in
			: 5 9
	5 9		: 1 2 3 4 5
	1 2 3 4 5		; carti2.out
	carti2.out		: 2 4
			; Consolă
	2 4		: Valid input
	==Explicație==		==Explicație==
	Intervalul [2, 4], deoarece 2 + 3 + 4 = 9		Intervalul [2, 4], deoarece 2 + 3 + 4 = 9
Line 45:		Line 45:
	n, x = map(int, input().split())		n, x = map(int, input().split())
	validate_input(n, x)		validate_input(n, x)
			print("Valid input")
	sp = [0] * (n + 1)		sp = [0] * (n + 1)
	for i in range(1, n + 1):		for i in range(1, n + 1):

Cata: Pagină nouă: ==Cerința== Un filipinez cultivat are X cărți pe care dorește să le vândă. Pentru aceasta, el merge pe strada Plopilor fără soț unde se află n case. Acesta știe că în fiecare dintre cele n case se vor vinde un număr de cărți. Filipinezul cultivat începe să vândă de la o casă a și trece pe la toate casele succesive până când nu mai are cărți de vândut. Determinați intervalul minim lexicografic [a, b] între care filipinezul să-și vândă căr...

2023-04-20T18:21:30Z

Pagină nouă: ==Cerința== Un filipinez cultivat are X cărți pe care dorește să le vândă. Pentru aceasta, el merge pe strada Plopilor fără soț unde se află n case. Acesta știe că în fiecare dintre cele n case se vor vinde un număr de cărți. Filipinezul cultivat începe să vândă de la o casă a și trece pe la toate casele succesive până când nu mai are cărți de vândut. Determinați intervalul minim lexicografic [a, b] între care filipinezul să-și vândă căr...

New page

==Cerința==
Un filipinez cultivat are X cărți pe care dorește să le vândă. Pentru aceasta, el merge pe strada Plopilor fără soț unde se află n case. Acesta știe că în fiecare dintre cele n case se vor vinde un număr de cărți.

Filipinezul cultivat începe să vândă de la o casă a și trece pe la toate casele succesive până când nu mai are cărți de vândut.

Determinați intervalul minim lexicografic [a, b] între care filipinezul să-și vândă cărțile, astfel încât să vândă un număr maxim de carți, mai mic sau egal cu X

==Date de intrare==
Fișierul de intrare carti2.in conține pe prima linie numerele n și X, iar pe a doua linie n numere naturale separate prin spații reprezntând numărul de cărți pe care le va vinde la fiecare casă.

==Date de ieșire==
Fișierul de ieșire carti2.out va conține pe prima linie numerele a și b, reprezentând minim lexicografic al numerelor caselor pentru care numărul de cărți maxim este vândut.

==Restricții și precizări==
* 1 ≤ n ≤ 100.000
* 1 ≤ X ≤ 1.000.000.000
* numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000
==Exemplu==
carti2.in

5 9
1 2 3 4 5
carti2.out

2 4
==Explicație==
Intervalul [2, 4], deoarece 2 + 3 + 4 = 9

==Rezolvare==
<syntaxhighlight lang="python">
import sys

Inf = 0x3f3f3f3f

sys.stdin = open('carti2.in', 'r')
sys.stdout = open('carti2.out', 'w')

def validate_input(n, x):
if not 1 <= n <= 100000:
raise ValueError("Invalid value for n. Must be between 1 and 100000.")
if not 1 <= x <= 1000000000:
raise ValueError("Invalid value for x. Must be between 1 and 1000000000.")

def read_input():
n, x = map(int, input().split())
validate_input(n, x)
sp = [0] * (n + 1)
for i in range(1, n + 1):
y = int(input())
sp[i] = sp[i-1] + y
return n, x, sp

def CautBin(x, poz, n, sp):
st = poz
dr = n
PozCautata = 0
while st <= dr:
mij = (st + dr) // 2
if sp[mij] - sp[poz-1] <= x:
PozCautata = mij
st = mij + 1
elif sp[mij] - sp[poz-1] > x:
dr = mij - 1
return PozCautata

def find_books(n, x, sp):
maxim = 0
st = 0
dr = 0
for i in range(1, n + 1):
poz = CautBin(x, i, n, sp)
if sp[poz] - sp[i-1] > maxim and sp[poz] - sp[i-1] <= x:
maxim = sp[poz] - sp[i-1]
st = i
dr = poz
return st, dr

if __name__ == "__main__":
try:
n, x, sp = read_input()
st, dr = find_books(n, x, sp)
print(st, dr)
except ValueError as ve:
print(str(ve))

</syntaxhighlight>

==Explicație cod==
Acesta este un program Python care primește date de intrare din fișierul "carti2.in" și scrie datele de ieșire în fișierul "carti2.out". În esență, programul primește un număr n și un număr x, reprezentând numărul de cărți și suma de bani disponibile, respectiv, și o listă de prețuri pentru fiecare carte. Scopul programului este de a găsi o pereche de indici (st, dr) astfel încât suma prețurilor de cărți de la st la dr să fie maximă și mai mică sau egală cu x.

Funcțiile definite în cod includ:

validate_input: Această funcție verifică dacă valorile n și x sunt valide și, în caz contrar, aruncă o excepție.
read_input: Această funcție primește datele de intrare și le prelucrează pentru a crea o listă sp care reprezintă suma cumulată a prețurilor pentru fiecare carte, începând cu prima carte.
CautBin: Această funcție implementează o căutare binară pentru a găsi poziția la care suma prețurilor de la poz până la mijlocul intervalului este mai mare sau egală cu x. Această funcție este apelată în cadrul funcției find_books.
find_books: Această funcție parcurge lista sp și pentru fiecare index i găsește indexul j astfel încât suma prețurilor de cărți de la i la j este maximă și mai mică sau egală cu x.
Blocul principal al programului apelează funcțiile read_input și find_books, apoi afișează indicii st și dr găsiți prin intermediul funcției find_books. Dacă valorile pentru n sau x sunt nevalide, programul va afișa un mesaj de eroare.