Editing 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 scoala2
: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