Danciu: Pagină nouă: 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...

2024-06-04T08:52:38Z

Pagină nouă: 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 <code>1</code> 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 <code>Q</code> întreb...

New page

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 <code>1</code> 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 <code>Q</code> întrebări de forma: Câte numere fibocel există în intervalul închis <code>[A, B]</code>?

= Date de intrare =
Fișierul de intrare <code>fibocel.in</code> conține pe prima linie numărul natural <code>Q</code>, iar pe următoarele <code>Q</code> linii se găsesc câte două numere naturale <code>A</code> şi <code>B</code> 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 <code>fibocel.out</code> va conține exact <code>Q</code> numere, câte unul pe o linie, reprezentând răspunsurile la cele <code>Q</code> întrebări, în ordinea în care ele apar în fişierul de intrare.

= Restricții și precizări =

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

= Exemplul 1 =
<code>fibocel.in</code>
1
15 16
<code>fibocel.out</code>
1

=== Explicație ===
<code>15(10) =1111(2)</code> nu este fibocel (are <code>4</code> biţi de <code>1</code> iar <code>4</code> nu este număr Fibonacci)

<code>16(10) =10000(2)</code> este fibocel (are <code>1</code> bit de <code>1</code> iar <code>1</code> este număr Fibonacci)

= Exemplul 2 =
<code>fibocel.in</code>
7
1 13
13 31
13 131
31 131
131 313
313 1313
1313 3131
<code>fibocel.out</code>
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>

1645 - Fibocel - Revision history