AjM: Pagină nouă: == Cerinţa == Se dă șirul lui Fibonacci: f1=1, f2=1, f3=2, f4=3, f5=5, …, definit astfel fk+2 = fk+1 + fk, k>2. Se dau Q query-uri de forma ab. Se cere să se afișeze pentru fiecare query fa, fb și suma elementelor fk din șirul lui Fibonacci cu a≤k≤b. == Date de intrare == Fișierul de intrare fibointerval.in conține pe prima linie numerele n si Q, iar pe următoarele Q linii câte două numere a si b reprezentând query-urile. == Date de ieșire == Fișierul de...

2024-06-03T16:58:48Z

Pagină nouă: == Cerinţa == Se dă șirul lui Fibonacci: f1=1, f2=1, f3=2, f4=3, f5=5, …, definit astfel fk+2 = fk+1 + fk, k>2. Se dau Q query-uri de forma ab. Se cere să se afișeze pentru fiecare query fa, fb și suma elementelor fk din șirul lui Fibonacci cu a≤k≤b. == Date de intrare == Fișierul de intrare fibointerval.in conține pe prima linie numerele n si Q, iar pe următoarele Q linii câte două numere a si b reprezentând query-urile. == Date de ieșire == Fișierul de...

New page

== Cerinţa ==
Se dă șirul lui Fibonacci: f1=1, f2=1, f3=2, f4=3, f5=5, …, definit astfel fk+2 = fk+1 + fk, k>2.

Se dau Q query-uri de forma ab. Se cere să se afișeze pentru fiecare query fa, fb și suma elementelor fk din șirul lui Fibonacci cu a≤k≤b.
== Date de intrare ==
Fișierul de intrare fibointerval.in conține pe prima linie numerele n si Q, iar pe următoarele Q linii câte două numere a si b reprezentând query-urile.
== Date de ieșire ==
Fișierul de ieșire fibointerval.out va conține pe fiecare linie, în ordine, rezultatul celor Q query-uri, cele 3 valori care trebuie afișate fiind separate prin câte un spațiu.
== Restricţii şi precizări ==
* 1 ≤ n ≤ 1000
* 1 ≤ Q ≤ 10000
* 1 ≤ a ≤ b ≤ n
== Exemplu ==
; fibointerval.in
10 3
1 3
3 5
2 8
; fibointerval.out
1 2 4
2 5 10
1 21 53
<br>

== Explicație ==
n=10 și Q=3.
Primul query: a=1, b=3, rezultă că f1=1, f3=2, iar suma elementelor cu indici cuprinși intre a și b este 4.Al doilea query: a=3, b=5, rezultă că f3=2, f5=5, iar suma elementelor cu indici cuprinși intre a și b este 10.Al treilea query: a=2, b=8, rezultă că f2=1, f8=21, iar suma elementelor cu indici cuprinși intre a și b este 53.
== Rezolvare ==
<syntaxhighlight lang="python" line>
def generate_fibonacci(n):
fibonacci = [1, 1]

for i in range(2, n):
fibonacci.append(fibonacci[i-1] + fibonacci[i-2])

return fibonacci

def main():
with open("fibointerval.in", "r") as fin:
n, Q = map(int, fin.readline().split())
queries = [tuple(map(int, fin.readline().split())) for _ in range(Q)]

fibonacci = generate_fibonacci(n)

with open("fibointerval.out", "w") as fout:
for a, b in queries:
fa = fibonacci[a - 1]
fb = fibonacci[b - 1]
fib_sum = sum(fibonacci[a - 1:b])
fout.write(f"{fa} {fb} {fib_sum}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

3015 - Fibo Interval - Revision history