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 ⩽ n ⩽ 100.000
• 1 ⩽ Q ⩽ 100.000
• 1 ⩽ a[i] ⩽ 1.000 pentru orice i=1..n
• pentru fiecare întrebare, 1 ⩽ x, s ⩽ 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 ⩽ 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.