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

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.")

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