# Cod sursa(job #2253622)

Utilizator Data 4 octombrie 2018 10:52:19 Fibo3 100 cpp done Arhiva de probleme 1.07 kb
``````#include <iostream>
#include <fstream>

using namespace std;

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

#define ll long long
#define MIN(a , b) (((a) < (b)) ? (a) : (b))
#define MAX(a , b) (((a) < (b)) ? (b) : (a))

int const nmax = 100000;
ll const lim = 2000000000000000;

ll fib[5 + nmax] , fibs = 0;

void computefib(){
fib[0] = fib[1] = 1;
int pos = 1;
while(fib[pos] <= lim){
fib[pos + 1] = fib[pos] + fib[pos - 1];
pos++;
//cout << pos << " " << fib[pos] << '\n';
}
fibs = pos - 1;
}

void solve(){
ll x , y , x2 , y2;
in >> x >> y >> x2 >> y2;
if(x2 < x)
swap(x , x2);
if(y2 < y)
swap(y2 , y);

ll result = 0;
for(int i = 1 ; i <= fibs ;i++){
ll startlin = fib[i] - y2;
ll stoplin = fib[i] - y;
//cout << fib[i] << " " << startlin << " " << stoplin << '\n';

result += MAX(0 , MIN(stoplin , x2) - (MAX(startlin , x) - 1));
}
out << result << '\n';
}

int main()
{
computefib();
int q;
in >> q;
for(int i = 1 ; i <= q ; i++)
solve();

return 0;
}
``````