3347 - Fibonacci3

Cerința

Se dă un şir format din n numere naturale. Se calculează suma elementelor oricărui subşir al şirului dat. Să se afle câte din sumele obţinute sunt termeni ai şirului lui Fibonacci.

Date de intrare

Fișierul de intrare fibonacci3IN.txt conține pe prima linie numărul n, iar pe următoarea linie n numere naturale.

Date de ieșire

Fișierul de ieșire fibonacci3OUT.txt va conține numărul sumelor care sunt termeni ai şirului lui Fibonacci. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

• 2 ≤ n ≤ 25
• numerele date sunt cel mult egale cu 1017

Exemplul 1:

fibonacci3IN.txt

2
3 18

fibonacci3OUT.txt

2

Explicație

Sumele obţinute sunt 3, 18 şi 21, dintre care 3 şi 21 sunt termeni ai şirului lui Fibonacci.

Exemplul 2:

fibonacci3IN.txt

1
3 18

fibonacci3OUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

import sys

NMAX = 2500000000000000225

def gen_fibo():
    fibonacci = [0, 1]
    x, y = 1, 1
    while x + y < NMAX:
        z = x + y
        fibonacci.append(z)
        y = x
        x = z
    return fibonacci

def cauta(fibonacci, valoare):
    st, dr = 0, len(fibonacci) - 1
    while st <= dr:
        mij = (st + dr) // 2
        if fibonacci[mij] == valoare:
            return True
        if valoare < fibonacci[mij]:
            dr = mij - 1
        else:
            st = mij + 1
    return False

def bkt(k, s, n, v, fibonacci):
    global nr
    if cauta(fibonacci, s):
        nr += 1
    if k < n:
        for i in range(k + 1, n + 1):
            bkt(i, s + v[i - 1], n, v, fibonacci)

def verifica_restrictii(n, v):
    if not (2 <= n <= 25):
        return False
    if any(x > 10**17 for x in v):
        return False
    return True

def main():
    global nr
    nr = 0

    with open("fibonacci3IN.txt", "r") as fin:
        n = int(fin.readline().strip())
        v = list(map(int, fin.readline().strip().split()))

    with open("fibonacci3OUT.txt", "w") as fout:
        if not verifica_restrictii(n, v):
            fout.write("Datele nu corespund restrictiilor impuse")
            return

        fibonacci = gen_fibo()
        for i in range(1, n + 1):
            bkt(i, v[i - 1], n, v, fibonacci)
        fout.write(str(nr))

if __name__ == "__main__":
    main()