== include(page="template/taskheader" task_id="fibo3") ==
Poveste şi cerinţă...
Fie şirul numerelor Fibonacci:
$F{~0~}=1, F{~1~}=1, F{~2~}=2, F{~3~}=3, F{~4~}=5 etc.$
Vom acoperi toate punctele laticiale de coordonate nenegative astfel:
* Daca pentru un punct $P(x,y), x+y$ este un număr Fibonacci, atunci lui $P$ îi asociem valoarea $1$.
* Daca pentru un punct $P(x,y), x+y$ nu este un număr Fibonacci, atunci lui $P$ îi asociem valoarea $0$.
h2. Cerinţă
Răspundeţi la $N$ întrebări de forma: _Dându-se un dreptunghi $D(x{~1~}, y{~1~}, x{~2~}, y{~2~})$, care este suma valorilor asociate punctelor din plan conţinute de dreptunghiul $D$?_
h2. Date de intrare
Fişierul de intrare $fibo3.in$ ...
Fişierul de intrare $fibo3.in$ conţine pe prima linie numărul $N$ de întrebări. Următoarele $N$ linii vor conţine câte patru numere naturale reprezentând câte un dreptunghi de query.
h2. Date de ieşire
În fişierul de ieşire $fibo3.out$ ...
În fişierul de ieşire $fibo3.out$ se vor găsi $N$ numere naturale, fiecare pe câte o linie, numărul de pe linia $K$ fiind răspunsul la cea de-a $K$-a întrebare.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100 000$
* $0 ≤ x{~1~} ≤ x{~2~} ≤ 10^15^$
* $0 ≤ y{~1~} ≤ y{~2~} ≤ 10^15^$
* Un punct $P(x,y)$ se numeşte punct laticial, dacă $x$ şi $y$ sunt numere întregi.
* Sirul numerelor Fibonacci este determinat de recurenţa $F{~N~} = F{~N-1~} + F{~N-2~}$
* Pentru $30%$ din teste coordonatele dreptunghiurilor nu depăşesc $1000$.
h2. Exemplu
table(example). |_. fibo3.in |_. fibo3.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
0 0 1 1
1 0 1 2
| 3
3
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="fibo3") ==
