== 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.
Liniile de la $2$ la $N+1$ 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 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.
* Pentru $30%$ din teste coordonatele dreptunghiurilor sunt maxim $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") ==
