Макс и числа без 11

Question

Можете помочь ускорить или переписать код?

ограничение по времени на тест: 2 секунды
ограничение по памяти на тест: 64 мегабайта
ввод: стандартный ввод
вывод: стандартный вывод

Макс сконструировал очередное электронное устройство. Оно должно было показывать двоичные числа:

1, 10, 11, 100, 101, 110, 111, 1000, . . . Но что-то пошло не так. По какой-то причине устройство оказалось неспособно отображать две единицы подряд, поэтому оно пропускает числа, в записи которых содержится 11:

1, 10, 100, 101, 1000, 1001, 1010, . . . Помогите Максу определить, какое число устройство покажет N-м по счёту.

Входные данные: Ввод содержит целое число N (1≤N≤10^9).

Выходные данные: Выведите N-е в порядке возрастания двоичное число, не содержащее двух единиц подряд.

Примеры:

входные данные: 3

выходные данные: 100

входные данные: 140

выходные данные: 1010100101

a=int(input())
i=0
d=0
while d != a:
    i += 1
    d+=int(not "11" in bin(i))
    if d == a:
        print(bin(i)[2:])

Answer 1

Вывел все подобные числа до 1000:

for k in range(1, 1000):
    if not '11' in str(bin(k)):
        print(str(bin(k))[2:])

Попробовал найти закономерность:

Количество чисел в каждой "группе": 1 1 2 3 5 8 13 21... ничего не напоминает?:)
Причем, внутри каждого блока если отбросить первые две цифры, оставшиеся числа будут точно совпадать со всеми числами до предыдущей группы. Получается фибоначчи внутри фибоначчи.

Во-первых, числа фибоначчи довольно быстро растут. 45-е число переходит за миллиард (максимальное N по условию задачи). Поэтому можно заранее собрать первые 45 чисел в список.

Во-вторых, т.к. "группы" чисел выше разбиты по количеству цифр, получив N, можно пройтись по списку чисел фибоначчи и точно узнать, в какой по счету группе находится искомое число (а значит, и количество её цифр).

Решение нашлось интуитивно (и внезапно, прошло все тесты).

В задаче есть пример 140 → 1010100101. Магия такая:

L = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...] (отбросил двойные единички)
    (1, 2, 3, 4, 5,  6,  7,  8,  9, 10,  11, ...)

140 >= 89  (10-е число); 140 -= 89 → 51
 51 >= 34  ( 8-е число);  51 -= 34 → 17
 17 >= 13  ( 6-е число);  17 -= 13 → 4
  4 >= 3   ( 3-е число);   4 -= 3  → 1
  1 >= 1   ( 1-е число);   1 -= 1  → 0
_______________________________________
            1010100101
           10 8 6  3 1

def fib(n):
    a, b = L = [1, 1]

    for k in range(n - 2):
        a, b = b, a + b
        L.append(b)

    return L

fib_list = fib(45)
fib_list[0] = 0 # две единицы вначале мешают.
fib_rvrs = list(reversed(fib_list))

def bubu(N):
    ones = [] # Будет собирать позиции единичек в числе

    while N > 0:
        for f in fib_rvrs:
            if N >= f:
                max_fib = f
                break

        N -= max_fib
        ones.append(fib_list.index(max_fib))

    # ones = [9, 7, 5, 3] -> 101010100
    #                        9 7 5 3
    result = ''
    ones += [0]

    for i in range(len(ones) - 1):
        result += '1'
        result += '0' * (ones[i] - ones[i + 1] - 1)

    return result


N = int(input())
print( bubu(N) )

Миллиардное число: 1010000100100001010101000001000101000101001

Ура!

Answer 2

Отличный ответ OPTIMUS PRIME объясняет как получить решение. Добавлю только две вещи.

Задача свелась к разложению числа по числам Фибоначчи. Вы скорее всего знакомы с разложением по степеням десятки и двойки. Скажем разложение числа 140 по степеням двойки имеет вид:

10001100b =
= 1 * 2^7 + 0 * 2^6 + 0 * 2^5 + 0 * 2^4 + 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 0 * 2^0 =
= 128 + 8 + 4 =
= 140

Разложение по числам Фибоначчи:

1010100101fib =
= 1 * fib(11) + 0 * fib(10) + 1 * fib(9) + 0 * fib(8) + 1 * fib(7) +
+ 0 * fib(6) + 0 * fib(5) + 1 * fib(4) + 0 * fib(3) + 1 * fib(2) =
= 89 + 34 + 13 + 3 + 1 = 
= 140

При разложении числа алгоритм один и тот-же для степеней двойки и для чисел Фибоначчи. Из разлагаемого числа последовательно вычитаем числа из ряда (степеней или Фибоначчи). Когда вычесть удаётся записываем единицу, иначе ноль:

140
 i   2^i   n - 2^i      бит  : fib(i+2) n - fib(i+2)  бит
 9:  512                     :    89    140 - 89 = 51  1
 8:  256                     :    55                   0
 7:  128 140 - 128 = 12  1   :    34     51 - 34 = 17  1
 6:   64                 0   :    21                   0
 5:   32                 0   :    13     17 - 13 =  4  1
 4:   16                 0   :     8                   0
 3:    8  12 -   8 =  4  1   :     5                   0
 2:    4   4 -   4 =  0  1   :     3      4 -  3 =  1  1
 1:    2                 0   :     2                   0
 0:    1                 0   :     1      1 -  1 =  0  1

Программа разлагающая число по ряду Фибоначчи:

import functools


@functools.lru_cache(None)
def fib(n):
    return n if n <= 1 else fib(n - 1) + fib(n - 2)


def bits(n):
    k = 0
    while fib(k) <= n:
        k += 1

    for i in reversed(range(2, k)):
        if fib(i) <= n:
            yield '1'
            n -= fib(i)
        else:
            yield '0'


print(*bits(int(input())), sep='')

$ echo 3 | python fib_bin.py 
100

$ echo 140 | python fib_bin.py 
1010100101

$ echo 1000000000 | python fib_bin.py 
1010000100100001010101000001000101000101001

БЛОГ НА HUSL

Макс и числа без 11

Ответы (2 шт):