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

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema FiboInterval:

#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;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #3015 FiboInterval

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3015 FiboInterval de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #3015 FiboInterval