Cod sursa(job #1992058)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 19 iunie 2017 12:03:25
Problema Fibo3 Scor 100
Compilator cpp Status done
Runda Simulare 15b Marime 1.07 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin ("fibo3.in"); ofstream fout ("fibo3.out");

typedef long long i64;

const i64 lim = 2e15 + 5;
const i64 inf = 1LL << 60;
i64 f[ 90 ];

int main() {
    int m = 0;
    f[ ++ m ] = 1;

    i64 a = 1, b = 1;
    while (a + b <= lim) {
        i64 c = a + b;
        f[ ++ m ] = c;
        a = b; b = c;
    }

    int n;
    fin >> n;
    for (int i = 1; i <= n; ++ i) {
        i64 c, d;
        fin >> a >> b >> c >> d;

        i64 ans = 0;
        for (int j = 1; j <= m; ++ j) {
            if (c + d < f[ j ]) break;

            if (a + b <= f[ j ]) {
                i64 x, y;

                if (f[ j ] - b <= c) {
                    x = b;
                } else {
                    x = f[ j ] - c;
                }

                if (a <= f[ j ] - d) {
                    y = d;
                } else {
                    y = f[ j ] - a;
                }

                ans += y - x + 1;
            }
        }

        fout << ans << "\n";
    }

    fin.close();
    fout.close();
    return 0;
}