2969 - Cauta Fibo

Cerinţa

Se citesc pe rând numere naturale nenule. Să se determine câte din numerele citite sunt termeni ai șirului lui Fibonacci.

Date de intrare

Fișierul de intrare cautafibo.in conține numere naturale nenule, separate prin spații.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran: "Datele sunt introduse corect.",fișierul de ieșire cautafibo.out va conține o singură valoare, reprezentând numărul termenilor Fibonacci care se regăsesc în fișierul de intrare. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• numerele din fișierul de intrare vor avea cel mult 10 cifre
• fișierul de intrare va conține cel mult 100.000 de numere naturale nenule

Exemple

Exemplul 1

cautafibo.in

5 10 89 1 7 9 8 1 6 55 19 13 55

ecran

Datele sunt introduse corect.

cautafibo.out

8

Exemplul 2

cautafibo.in

1 3 5 8 13 21 34 55 89 144

ecran

Datele sunt introduse corect.

cautafibo.out

10

Exemplul 3

cautafibo.in

-5 2 7 9 11 13 15

ecran

Datele nu corespund restricțiilor impuse.

cautafibo.out

Rezolvare

# 2969 - Cauta Fibo
def este_valid(fisier_intrare):
    try:
        with open(fisier_intrare, 'r') as f:
            for line in f:
                nums = line.strip().split()
                for num in nums:
                    if not num.isnumeric() or int(num) < 1 or len(num) > 10:
                        print("Datele nu corespund restricțiilor impuse.")
                        return False
        print("Datele sunt introduse corect.")
        return True
    except:
        print("Datele nu corespund restricțiilor impuse.")
        return False

def rezolva(fisier_intrare):
    if not este_valid(fisier_intrare):
        return

    with open(fisier_intrare, 'r') as f, open('cautafibo.out', 'w') as g:
        a = [1, 1]
        while a[-1] <= 10000000001:
            a.append(a[-1] + a[-2])
        cnt = 0
        for line in f:
            nums = line.strip().split()
            for num in nums:
                x = int(num)
                poz = -1
                st, dr = 0, len(a) - 1
                while st <= dr:
                    m = (st + dr) // 2
                    if x <= a[m]:
                        poz = m
                        dr = m - 1
                    else:
                        st = m + 1
                if a[poz] == x:
                    cnt += 1
        g.write(str(cnt))

def main():
    rezolva('cautafibo.in')

main()