# PBinfo #3015 – FiboInterval – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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

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ă \({f}_{1}=1\), \({f}_{3}=2\), iar suma elementelor cu indici cuprinși intre \(a\) și \(b\) este 4.
Al doilea query: \(a=3\), \(b=5\), rezultă că \({f}_{3}=2\), \({f}_{5}=5\), iar suma elementelor cu indici cuprinși intre \(a\) și \(b\) este 10.
Al treilea query: \(a=2\), \(b=8\), rezultă că \({f}_{2}=1\), \({f}_{8}=21\), iar suma elementelor cu indici cuprinși intre \(a\) și \(b\) este 53.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
#define last 220
using namespace std;
ifstream fin ("fibointerval.in");
ofstream fout("fibointerval.out");
short int x[1005][225];
void Fibo (int p){
    int i;
    for (i=last; i>=1; i--){
        x[p][i] += x[p-1][i] + x[p-2][i];
        x[p][i-1] += x[p][i] / 10;
        x[p][i] %= 10;
    }
}
void afisare (int p){
    int i;
    for (i=1; i<=last; i++)
        if (x[p][i])
        break;
    for (;i<=last; i++)
        fout << x[p][i];
    fout << " ";
}
int afis[225];
void sumInterval (int a, int b){
    int i;
    for (i=0; i<=last; i++)
        afis[i] = x[b+2][i];
    for (i=last; i>=1; i--){
        afis[i] -= x[a+1][i];
        if (afis[i]<0){
            afis[i] += 10;
            afis[i-1] --;
        }
    }
    for (i=1; i<=last; i++)
        if(afis[i])
        break;
    for (; i<=last; i++)
        fout << afis[i];
    fout << "\n";
}
int main()
{
    int n, i, Q, q, a, b;
    fin >> n >> Q;
    x[1][last] = 1;
    x[2][last] = 1;
    for (i=3; i<=n+2; i++)
        Fibo(i);
//    for (i=1; i<=n+2; i++)
//        afisare(i), fout << "\n";
    for (q=1; q<=Q; q++){
        fin >> a >> b;
        afisare(a);
        afisare(b);
        sumInterval(a,b);
    }
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3015)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3015/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3015/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)