3176 - Fibonacci perechi

Se consideră şirul Fibonacci, definit astfel: f1=1, f2=1, fn=fn−1+fn−2, dacă n>2.

Cerință

Se dau perechi de numere a și b cu a ≤ b. Să se calculeze pentru câte perechi fb este multiplu de fa.

Date de intrare

Fișierul de intrare fibo0in.txt conține pe fiecare linie câte două numere a și b cu semnificația din enunț .

Date de ieșire

Fișierul de ieșire fibo0out.txt va conține pe prima linie numărul N, reprezentând numărul de perechi ce respectă condiția impusă .

Restricții de precizări

• Se vor citi până la 1.000.000 de perechi
• Numerele citite vor fi numere naturale strict mai mari decât 2 și mai mici decât 2.000.000.002

Exemplul 1

fibo0in.txt

4 9

4 8

10 12

7 21

fibo0out.txt

Datele de intrare corespund restrictiilor impuse.

2

Exemplul 2

fibo0in.txt

4 fd

a 8

10 hsj2

7 21

fibo0out.txt

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

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

def fibonacci(n): # functia de generare a sirului Fibonacci

   fib = [0, 1]
   for i in range(2, n+1):
       fib.append(fib[i-1] + fib[i-2])
   return fib

def count_multiples(perechi): # functia de rezolvare

   max_n = max(max(pair) for pair in perechi)
   fib = fibonacci(max_n)
   count = 0
   for a, b in pairs:
       if fib[b] % fib[a] == 0:
           count += 1
   return count

def validare(perechi): # functia de validare a datelor de intrare

   if len(perechi) > 1000000:
       raise ValueError
   for pair in pairs:
       if not all(2 < i < 2000000002 for i in pair):
           raise ValueError
   file_out.write("Datele de intrare corespund restrictiilor impuse.\n")

if __name__ == '__main__':

   file_in = open("fibo0in.txt", "r")  # declararea fisierelor
   file_out = open("fibo0out.txt", "w")  # fisierul out trebuie declarat cu optiunea "w" (write)

   try:
       pairs = [tuple(map(int, line.split())) for line in file_in.readlines()]  # citirea perechilor

       validare(pairs)  # apelul functiei de validare
       result = count_multiples(pairs)  # apelul functiei de rezolvare
       file_out.write(str(result))

   except ValueError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse.")
   except IndexError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>

Explicație

f4=3 , iar f9=34

care NU este multiplu de 3

f4=3 , iar f8=21

care este multiplu de 3

f10=55 , iar f12=144

care NU este multiplu de 55

f7=13 , iar f21=10946

care este multiplu de 13