Oros Ioana Diana: Pagină nouă: = 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...

2024-05-18T19:29:20Z

Pagină nouă: = 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...

New page

= 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>

3347 - Fibonacci3 - Revision history