1645 - Fibocel

Toată 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ța

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 și precizări

• 1 ≤ Q ≤ 50.000
• 1 ≤ A ≤ B ≤ 1015
• Şirul Fibonacci se defineşte astfel: , pentru
• Pentru 40% din teste B ≤ 1.000.000

Exemplul 1

fibocel.in

1
15 16

fibocel.out

1

Explicație

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)

Exemplul 2

fibocel.in

7
1 13
13 31
13 131
31 131
131 313
313 1313
1313 3131

fibocel.out

13
14
76
63
97
421
667

Rezolvare

<syntaxhighlight lang="python3"> def is_fibocel(n):

   bit_count = 0
   while n > 0:
       if n % 2 == 1:
           bit_count += 1
       n //= 2

   previous = 0
   current = 1
   while current <= bit_count:
       if current == bit_count:
           return True
       previous, current = current, previous + current

   return False

def count_fibocel_numbers(a, b):

   count = 0
   for num in range(a, b + 1):
       if is_fibocel(num):
           count += 1

   return count

def main():

   with open("fibocel.in", "r") as input_file:
       q = int(input_file.readline())

   with open("fibocel.out", "w") as output_file:
       for _ in range(q):
           a, b = map(int, input_file.readline().split())
           fibocel_count = count_fibocel_numbers(a, b)
           output_file.write(str(fibocel_count) + "\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>