2276 - Cb

Enunț

Se consideră un șir a[1], a[2], …, a[n] de numere naturale. Se dau și T intervale închise de forma [x, y], cu x ≤ y.

Cerință

Pentru fiecare din cele T intervale de forma [x, y] trebuie să răspundeți la întrebarea: câte numere din șir aparțin intervalului [x, y]?

Date de intrare

Programul citește de la tastatură numerele n și T, apoi n numere naturale, separate prin spații, a[1], a[2], …, a[n]. Pe următoarele T linii se află câte două numere naturale x și y reprezentând un interval [x, y].

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele de intrare corespund restricțiilor impuse." Programul va afișa pe ecran T linii. Pe fiecare linie i (i=1..T) se va afla un singur număr natural reprezentând răspunsul la a i-a întrebare. În caz contrar, se va afișa pe ecran: "Datele de intrare nu corespund restricțiilor impuse."

Restricții și precizări

• 1 ≤ n, T ≤ 200 000
• 0 ≤ a[i] ≤ 2 000 000 000
• 0 ≤ x ≤ y ≤ 2 000 000 000

Exemplul 1

Intrare

9 7

6 1 3 5 3 3 9 20 9

4 10

0 100

0 1

500 506

3 3

10 18

3 9

Ieșire

Datele de intrare corespund restrictiilor impuse.

4

9

1

0

3

0

7

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line="1" start="1">

def validate_input(n, T, a, intervals):

   if len(a) != n:
       return False
   for x, y in intervals:
       if x > y:
           return False
   return True

def count_numbers_in_intervals(n, T, a, intervals):

   if not validate_input(n, T, a, intervals):
       return []

   counts = []
   for x, y in intervals:
       count = 0
       for num in a:
           if x <= num <= y:
               count += 1
       counts.append(count)

   return counts

if __name__ == '__main__':

   n, T = map(int, input().split())
   a = list(map(int, input().split()))

   intervals = []
   for i in range(T):
       x, y = map(int, input().split())
       intervals.append((x, y))
   if validate_input(n, T, a, intervals):
       print("Datele de intrare corespund restrictiilor impuse.")
       counts = count_numbers_in_intervals(n, T, a, intervals)
       for count in counts:
           print(count)
   else:
       print("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>

Explicatie

Acest program citește întâi valorile n și T de la intrare folosind map(int, input().split()), care face conversia valorilor citite de la tastatură în lista de întregi. Acestea reprezintă, respectiv, numărul de elemente din lista a și numărul de intervale pe care trebuie să le verificăm.

Următoarea linie citește lista a de n elemente de la intrare, folosind list(map(int, input().split())). Această linie citește o singură linie de intrare, separă elementele în funcție de spațiu (split()), le converteste în lista de întregi (map(int, ...)) și creează lista finală (list(...)).

În continuare, linia for i in range(T): iterăm prin fiecare interval și adăugăm intervalele la lista de intervale folosind linia intervals.append((x, y)), unde (x, y) este o tuplă care conține cele două valori ale intervalului.

Apelăm funcția count_numbers_in_intervals cu argumentele necesare și apoi afișăm rezultatele într-un format specificat.

Funcția count_numbers_in_intervals primește numărul de elemente din lista a, numărul de intervale, lista de numere a și o listă de intervale și returnează o listă cu numărul de elemente din fiecare interval.

Funcția validate_input verifică dacă datele de intrare sunt valide și returnează True dacă sunt și False în caz contrar. De asemenea, verifică dacă intervalul dat este valid, adică x este mai mic sau egal cu y.

Pentru a verifica dacă un număr se află într-un interval dat, iterăm prin lista a și verificăm dacă fiecare element este mai mare sau egal cu limita inferioară x și mai mic sau egal cu limita superioară y. Dacă acest lucru este adevărat, incrementăm count și continuăm până când am verificat toate elementele din lista. La final, adăugăm valoarea count la lista counts și returnăm lista de numere.