| Fişierul intrare/ieşire: | fibo3.in, fibo3.out | Sursă | Stelele Informaticii 2010 |
| Autor | Serban Andrei Stan | Adăugată de |  Serban Andrei Stan •savim |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 10096 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | fibo3.out |
|---|---|
| 2 0 0 1 1 1 0 1 2 | 3 3 |
Trebuie sa te autentifici pentru a trimite solutii. Click aici
remote content
