View source for 3347 - Fibonacci3

= Cerința =
Se dă un şir format din <code>n</code> 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 <code>fibonacci3IN.txt</code> conține pe prima linie numărul <code>n</code>, iar pe următoarea linie <code>n</code> numere naturale.

= Date de ieșire =
Fișierul de ieșire <code>fibonacci3OUT.txt</code> 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 =

* <code>2 ≤ n ≤ 25</code>
* numerele date sunt cel mult egale cu <code>1017</code>

= Exemplul 1: =
<code>fibonacci3IN.txt</code>
 2
 3 18
<code>fibonacci3OUT.txt</code>
 2

=== Explicație ===
Sumele obţinute sunt <code>3</code>, <code>18</code> şi <code>21</code>, dintre care <code>3</code> şi <code>21</code> sunt termeni ai [[Fibonacci number|şirului lui Fibonacci]].

== Exemplul 2: ==
<code>fibonacci3IN.txt</code>
 1
 3 18
<code>fibonacci3OUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
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()

</syntaxhighlight>