2239 - Pow2

Se consideră un șir a[1], a[2],…, a[n] de numere naturale nenule.

Cerință

Să se determine câte perechi de indici (i, j), 1 ≤ i < j ≤ n, există cu proprietatea că suma a[i] + a[j] este egală cu o putere a lui 2.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi cele n numere naturale nenule, separate prin spații.

Date de ieșire

Programul va afișa pe ecran un singur număr natural reprezentând numărul de perechi de indici distincți (i, j) cu proprietatea că suma a[i] + a[j] este egală cu o putere a lui 2.

Restricții și precizări

• 2 ≤ n ≤ 100.000
• 1 ≤ a[i] ≤ 1.000.000.000, pentru orice i = 1..n
• Numerele care sunt puteri ale lui 2 sunt 1, 2, 4, 8, 16, 32, …

Exemplul 1

Intrare

4

3 5 3 13

Ieșire

Datele de intrare corespund restrictiilor impuse.

4

Exemplul 2

Intrare

4

a

Ieșire

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

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

def verificare_restrictii(nr_n, nr_a): # functia de verificare a datelor de intrare

   if 2 <= nr_n <= 10**5 and all(1 <= a_i <= 10**9 for a_i in nr_a):
       return True
   else:
       return False

def numar_perechi(nr_n, nr_a):

   # Generăm toate puterile lui 2 până la 2^30
   puteri_de_doi = [2**i for i in range(31)]

   # Inițializăm un contor pentru fiecare număr posibil din șir
   contor = [0]*2000001

   # Inițializăm numărul de perechi cu 0
   nr_perechi = 0

   # Parcurgem fiecare element din lista a
   for i in range(nr_n):
       # Pentru fiecare element, parcurgem lista de puteri ale lui 2
       for putere in puteri_de_doi:
           # Dacă puterea lui 2 este mai mică decât numărul curent, trecem la următoarea putere
           if putere < nr_a[i]:
               continue

           # Calculăm numărul pe care îl căutăm în contor
           numar_cautat = putere - nr_a[i]

           # Dacă numărul căutat este în intervalul contorului
           if numar_cautat <= 2000000:
               # Adăugăm la numărul de perechi numărul de apariții al numărului căutat
               nr_perechi += contor[numar_cautat]

       # Dacă numărul curent este în intervalul contorului
       if nr_a[i] <= 2000000:
           # Incrementăm contorul pentru numărul curent
           contor[nr_a[i]] += 1

   return nr_perechi

if __name__ == '__main__':

   try:
       n = int(input("Introduceti numarul n: "))     # citirea numarului de linii si coloane
       a = list(map(int, input().split()))

       if verificare_restrictii(n, a):             # verificam datele de intrare
           print("Datele de intrare corespund restrictiilor impuse.")
           print(numar_perechi(n, a))                           # apelam functia de rezolvare
       else:
           print("Datele de intrare nu corespund restrictiilor impuse.")
   # ne asteptam la 2 tipuri de erori din cauza datelor de intrare, le tratam corespunzator
   except ValueError:
       print("Datele de intrare nu corespund restrictiilor impuse.")
   except IndexError:
       print("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>

Explicatii

Cele patru perechi de indici sunt: (1,2), (1,4), (2,3), (3,4).