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.

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ă: Valid input

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)
   print("Valid input")
   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.