1248 - carti2

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.