Cod sursa(job #466133)

Utilizator Mishu91Andrei Misarca Mishu91 Data 26 iunie 2010 11:01:07
Problema Fibo3 Scor 100
Compilator cpp Status done
Runda Stelele Informaticii 2010, gimnaziu si clasa a IX-a, Ziua 2 Marime 0.65 kb
#include <fstream>

using namespace std;

const long long MAX_F = 2000000000000000LL;
const int MAX_N = 100005;

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

int N;
long long F[MAX_N], x1, y1, x2, y2;
int Nf = 2;

int main() {
	F[1] = 1, F[2] = 2;
	for(; F[Nf] <= MAX_F;) {
		++Nf;
		F[Nf] = F[Nf-1] + F[Nf-2];
	}

    fin >> N;

	for(int i = 1; i <= N; ++i) {
		fin >> x1 >> y1 >> x2 >> y2;
        long long sol = 0;

		for(int j = 1; j <= Nf; ++j) {
			if(F[j] < x1 + y1) continue;
			if(F[j] > x2 + y2) break;

			long long xmin = max(x1, F[j] - y2);
			long long xmax = min(x2, F[j] - y1);

			sol += xmax - xmin + 1;
		}

		fout << sol << "\n";
	}
}