Fişierul intrare/ieşire:fibo3.in, fibo3.outSursăStelele Informaticii 2010
AutorSerban Andrei StanAdăugată desavimSerban Andrei Stan savim
Timp execuţie pe test0.25 secLimită de memorie10096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Fibo3

Fie şirul numerelor Fibonacci:
F0=1, F1=1, F2=2, F3=3, F4=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.

Cerinţă

Răspundeţi la N întrebări de forma: Dându-se un dreptunghi D(x1, y1, x2, y2), care este suma valorilor asociate punctelor din plan conţinute de dreptunghiul D?

Date de intrare

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.

Date de ieşire

Î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.

Restricţii

  • 1 ≤ N ≤ 100 000
  • 0 ≤ x1 ≤ x2 ≤ 1015
  • 0 ≤ y1 ≤ y2 ≤ 1015
  • 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 FN = FN-1 + FN-2
  • Pentru 30% din teste coordonatele dreptunghiurilor nu depăşesc 1000.

Exemplu

fibo3.infibo3.out
2
0 0 1 1
1 0 1 2
3
3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content