1248 - carti2: Difference between revisions
No edit summary |
No edit summary |
||
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ă | ||
: | : 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(" | 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(" | 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(" | 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== | ||
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. | |||
Î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 | 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 | |||
CautBin: | 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 | |||
Blocul principal | 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. |
Revision as of 06:47, 3 May 2023
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. Î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
- 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
- Consolă
- Input valid
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("Valoare invalidă pentru n. Trebuie să fie între 1 și 100000.") if not 1 <= x <= 1000000000: raise ValueError("Valoare invalidă pentru x. Trebuie să fie între 1 și 1000000000.")
def read_input():
n, x = map(int, input().split()) validate_input(n, x) print("Input valid") 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
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.
Î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.
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.
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".
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.