| Fişierul intrare/ieşire: | fibocel.in, fibocel.out | Sursă | Urmasii lui Moisil 2016, Clasa a 10-a |
| Autor | Cosmin-Mihai Tutunaru | Adăugată de |  Paul Diac •diac_paul |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Fibocel
Toata lumea ştie că Fibocel este pasionat de numere şi că vrea să iasă în evidenţă cu orice preţ. Într-o zi, el s-a decis să numească un număr fibocel (după numele lui) dacă numărul de biţi egali cu 1 din reprezentarea binară a numărului este un număr Fibonacci.
Cum asta nu e de ajuns pentru el, Fibocel s-a decis să propună şi o problemă la concursul lui preferat de la Iaşi.
Cerinţă
Să se raspundă la Q întrebări de forma: Câte numere fibocel există în intervalul închis [A, B] ?
Date de intrare
Fişierul de intrare fibocel.in conţine pe prima linie numărul natural Q, iar pe următoarele Q linii se găsesc câte două numere naturale A şi B separate prin exact un spaţiu, reprezentând extremităţile intervalului la care se referă întrebarea.
Date de ieşire
Fişierul de ieşire fibocel.out va conţine exact Q numere, câte unul pe o linie, reprezentând răspunsurile la cele Q întrebări, în ordinea în care ele apar în fişierul de intrare.
Restricţii
- 1 ≤ Q ≤ 50.000
- 1 ≤ A ≤ B ≤ 1015
- Şirul Fibonacci se defineşte astfel: F0=F1=1; Fn=Fn-1+Fn-2, pentru n ≥ 2
- Pentru 40% din teste B ≤ 1.000.000
Exemplu
| fibocel.in | fibocel.out | Explicaţie |
|---|---|---|
| 1 15 16 | 1 | 15(10)=1111(2) nu este fibocel (are 4 biţi de 1 iar 4 nu este număr Fibonacci) 16(10)=10000(2) este fibocel (are 1 bit de 1 iar 1 este număr Fibonacci) |
| 7 1 13 13 31 13 131 31 131 131 313 313 1313 1313 3131 | 13 14 76 63 97 421 667 | . |
