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

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>