Editing 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 <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>