Cerința

Se dă șirul lui Fibonacci: ${f}_{1}=1$, ${f}_{2}=1$, ${f}_{3}=2$, ${f}_{4}=3$, ${f}_{5}=5$, …, definit astfel ${f}_{k+2}$ = ${f}_{k+1}$ + ${f}_{k}$, $k>2$.

Se dau $Q$ query-uri de forma $a b$. Se cere să se afișeze pentru fiecare query ${f}_{a}$, ${f}_{b}$ și suma elementelor ${f}_{k}$ 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

este 53.

#include <bits/stdc++.h>


using namespace std;

ifstream cin("fibointerval.in");
ofstream cout("fibointerval.out");

struct poz
{
    int n;
    char C[1001];
}F[1005];

int n , k , a , b;

poz aduna(poz a , poz b)
{
    poz s = {0 , {0}};
    s.n = a.n;
    int t = 0;
    for(int i = 1 ; i <= a.n ; i++)
    {
        int c = a.C[i] + b.C[i] + t;
        s.C[i] = c % 10;
        t = c / 10;
    }
    if(t > 0)
    {
        s.n++;
        s.C[s.n] = t;
    }
    return s;
}


poz scade(poz a , poz b)
{
    int t = 0;
    for(int i = 1 ; i <= a.n ; i++)
    {
        int c = a.C[i] - b.C[i] + t;
        if(c < 0)
        {
            a.C[i] = 10 + c;
            t = -1;
        }
        else
        {
            a.C[i] = c;
            t = 0;
        }
    }
    while(a.C[a.n] == 0) a.n--;
    return a;
}

void afisare(poz a)
{
    for(int i = a.n ; i >= 1 ; i--)
        cout << (int)a.C[i];
}

int main()
{
    cin >> k >> n;
    F[1] = {1 , {0 , 1}};
    F[2] = {1 , {0 , 1}};
    for(int i = 3 ; i <= k +2; i++)
        F[i] = aduna(F[i - 1] , F[i - 2]);
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> a >> b;
        afisare(F[a]);
        cout << " ";
        afisare(F[b]);
        cout << " ";
        afisare(scade(F[b + 2] , F[a + 1]));
        cout << '\n';
    }
}