View source for 3015 - Fibo Interval

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