4265 - perechiAB

Sursa: 4265 - perechiAb

---

Cerinţa

Se dă un șir v1, v2, …, vn de numere naturale nenule și de asemenea se dau două numere naturale nenule A și B. Să se determine numărul perechilor (vi , vj) cu i < j și A ≤ vi + vj ≤ B.

Date de intrare

Programul citește de la tastatură numărul n, apoi șirul de n numere naturale, separate prin spații, iar la final se citesc numerele naturale nenule A și B.

Date de ieșire

Programul va afișa pe ecran numărul de perechi care îndeplinesc condițiile cerute.

Restricţii şi precizări

• 3 ≤ n ≤ 160.000
• 1 ≤ A ≤ B ≤ 2.000.000.000
• 1 ≤ vi ≤ 1.000.000.000

Exemplu

Intrare

5

1 2 3 4 5

7 10

Ieșire

4

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 4265 - perechiAB

n = int(input()) v = list(map(int, input().split())) A, B = map(int, input().split())

count = 0 for i in range(n-1):

   for j in range(i+1, n):
       if A <= v[i] + v[j] <= B:
           count += 1

print(count)

Rezolvare ver 1.1

def validate_input(n, v, A, B):

   if n < 3 or n > 160000:
       print("Datele nu corespund restricțiilor impuse")
       return False
   for i in range(n):
       if v[i] < 1 or v[i] > 1000000000:
           print("Datele nu corespund restricțiilor impuse")
           return False
   if A < 1 or B > 2000000000 or A > B:
       print("Datele nu corespund restricțiilor impuse")
       return False
   print("Datele sunt introduse corect.")
   return True

def numar_perechi(n, v, A, B):

   count = 0
   for i in range(n-1):
       for j in range(i+1, n):
           if A <= v[i] + v[j] <= B:
               count += 1
   return count

def read_input():

   n = int(input())
   v = list(map(int, input().split()))
   A, B = map(int, input().split())
   if not validate_input(n, v, A, B):
       exit()
   return n, v, A, B

if __name__ == '__main__':

   n, v, A, B = read_input()
   count = numar_perechi(n, v, A, B)
   if count is not None:
       print("Datele sunt introduse corect.")
       print(count)
   else:
       print("Datele nu corespund restricțiilor impuse.")

</syntaxhighlight>

Explicație rezolvare

validate_input(n, v, A, B): Această funcție verifică dacă datele de intrare sunt valide sau nu. Aceasta verifică dacă valorile n, v, A și B respectă condițiile specifice impuse în enunț. În cazul în care nu respectă, afișează un mesaj de eroare și returnează False, altfel, returnează True.

numar_perechi(n, v, A, B): Această funcție calculează numărul de perechi de numere din vectorul v care se încadrează între valorile A și B, și returnează acest număr.

read_input(): Această funcție citește datele de intrare (numărul de elemente din vectorul v, valorile vectorului v, valorile A și B) de la tastatură și le validează folosind funcția validate_input(). Dacă datele sunt corecte, returnează-le, altfel se termină programul.

Blocul if __name__ == '__main__': este blocul principal de cod care execută programul. Aceasta apelează funcția read_input() pentru a obține datele de intrare valide, apoi apelează funcția numar_perechi(n, v, A, B) pentru a calcula numărul de perechi de numere din vectorul v care se încadrează între valorile A și B, și afișează rezultatul.