Editing 2443 - cb2

Se consideră un șir de numere naturale nenule '''a[1]''', '''a[2]''', …, '''a[n]'''. Asupra șirului se efectuează '''Q''' interogări. Fiecare interogare este dată de o pereche '''(x, s)''': care este indicele maxim '''p''' cu proprietatea că '''a[i] ≤ x''', pentru orice '''i=1..p''' și în plus '''a[1] + a[2] + ... + a[p] ≤ s'''?
== Cerinţa ==
Trebuie să răspundeți la fiecare din cele '''Q''' întrebări.
== Date de intrare ==
Programul citește de la tastatură numărul '''n''', iar apoi '''n''' numere naturale, separate prin spații, reprezentând elementele șirului. Apoi se citește valoarea '''Q''' și la final se citesc '''Q''' perechi de forma '''(x, s)''' reprezentând întrebările.
== Date de ieșire ==
Programul va afișa pe câte o linie la ecran '''Q''' valori reprezentând răspunsurile la întrebări.
== Restricţii şi precizări ==
* '''1 &les; n &les; 100.000'''
* '''1 &les; Q &les; 100.000'''
* '''1 &les; a[i] &les; 1.000''' pentru orice '''i=1..n'''
* pentru fiecare întrebare, '''1 &les; x, s &les; 1.000.000.000'''
== Exemplul 1 ==
;Intrare
 9
 5 3 1 7 4 9 8 2 6
 6
 8 10
 4 20
 6 20
 6 8
 10 100
 10 20
;Iesire
 Datele de intrare corespund restrictiilor impuse
 3 
 0
 3
 2
 9
 5
== Exemplul 2 ==
;Intrare
 5
 1 2 3 4 5000
 3
 10 20
 20 30
 30 40
;Iesire
 Datele de intrare nu corespund restrictiilor impuse
== Rezolvare ==
<syntaxhighlight lang="python" line>
n = int(input())
a = list(map(int, input().split()))
Q = int(input())
queries = [list(map(int, input().split())) for _ in range(Q)]

if not (1 <= n <= 100000):
    print("Datele de intrare nu corespund restrictiilor impuse")
elif not all(1 <= ai <= 1000 for ai in a):
    print("Datele de intrare nu corespund restrictiilor impuse")
elif not (1 <= Q <= 100000):
    print("Datele de intrare nu corespund restrictiilor impuse")
elif not all(1 <= x <= 1000000000 and 1 <= s <= 1000000000 for x, s in queries):
    print("Datele de intrare nu corespund restrictiilor impuse")
else:
    print("Datele de intrare corespund restrictiilor impuse")

    for x, s in queries:
        p = 0
        total = 0
        while p < n and a[p] <= x and total + a[p] <= s:
            total += a[p]
            p += 1
        print(p)

</syntaxhighlight>
== Explicatie ==
 La prima întrebare, '''x=8''', '''s=10'''. Indicele maxim este '''3''' pentru că primele trei valori din șir sunt mai mici sau egale cu '''8''', iar '''5 + 3 + 1 &les; 10'''.
 La a doua întrebare, răspunsul este '''0''' deoarece primul număr din șir este '''5''' care este mai mare decât '''x=4'''.
 La a cincea întrebare, '''x=10''' și '''s=100'''. Răspunsul este chiar lungimea șirului.