Я наткнулся на эту программную задачу. Я думал, что это легко, но вместо этого потратил на это несколько часов! Вы можете найти описание проблемы и средство проверки вывода на странице https://code.google.com/codejam/contest/4284486/dashboard

Problem
A “0/1 string” is a string in which every character is either 0 or 1. There are two operations that can be performed on a 0/1 string:
switch: Every 0 becomes 1 and every 1 becomes 0. For example, "100" becomes "011".
reverse: The string is reversed. For example, “100” becomes “001”.
Consider this infinite sequence of 0/1 strings:
S0 = “”
S1 = “0”
S2 = “001”
S3 = “0010011”
S4 = “001001100011011”
…
SN = SN-1 + “0” + switch(reverse(SN-1)).
You need to figure out the Kth character of Sgoogol, where googol = 10100.

Проблема требует, чтобы вы разобрались с последовательностью. Правило создания новых элементов является частью описания проблемы: SN = SN-1 + “0” + switch(reverse(SN-1)).

Сложность заключается в том, что элемент последовательности для его генерации - это 10 ** 100-й!

Если вы не знаете, может ли ваш компьютер обрабатывать вычисления порядка 10 ** 100 (я не знал), вы можете провести небольшой тест: попробуйте запустить

>>> for _ in range(10**100): pass
...

и вы увидите, что даже pass - это слишком много для выполнения такого количества раз. Невозможно построить всю последовательность вплоть до элемента гугол.

Не имея представления о том, как добиться прогресса, я начал пытаться ответить на другой вопрос: можно ли вычислить количество битов в S_googol без генерации элемента?

Конечно. Вы знаете, что n-й элемент - это просто n-1-й элемент, a 0, а n-1-й элемент перевернут, а НЕ. То есть

Если вы продолжите расширять это рекурсивное выражение, вы начнете замечать закономерности и сможете сделать вывод, что

Таким образом, длина гугольного элемента последовательности составляет около 2**10**100 бит.

Это много! Я начал сомневаться, что существует какая-либо эффективная процедура для вычисления всей строки - или что я мог бы ее найти .

Идея: вы знаете, что средний элемент S_googol равен 0. Фактически, S_googol построен с использованием S_googol-1, 0 и (некоторые манипуляции с битами) S_googol-1. Тогда середина равна 0. По той же причине на 1/4 узора должен быть еще 0. В то время как на 3/4 узора… 1, так как это тот же 0 на 1/4, но перевернутый.

Могу ли я использовать эту идею, чтобы прыгать по шаблону, пока не узнаю цифру в позиции K?

да. Оказывается, могу. Я запустил код на S4, и он сработал! За исключением того, что ... сложность процедуры логарифмична по отношению к размеру шаблона, что означает, что в случае S_googol порядок равен 10 ** 100 \! Как объяснялось выше ... это уже слишком.

Даже идея, которая кажется умной, не более эффективна, чем первый грубый подход!

Еще одна идея: в описании задачи указано, что K будет не больше 10 ** 18. Если это правда, почему бы не перейти от середины паттерна к наименьшей степени двойки, которая наиболее близка к 10 ** 18, и не использовать вышеизложенную идею? Поскольку размер задачи намного меньше, это могло сработать!

Но. Чтобы найти требуемую степень двойки, вам нужно либо решить

или вам нужно начать с 10**18 и добавить +1, проверяя на каждой итерации, является ли результат степенью 2 или нет.

Оба подхода потерпели неудачу. Первое, потому что Wolfram Alpha не хотела его решать; второй, потому что степени двойки явно не плотные - алгоритм зависает на слишком долгое время.

Другая идея: почему бы не начать с начала паттерна (зная, что вы всегда будете слева от целого S_googol), расширяя его до тех пор, пока не достигнете точки, в которой повторное использование первоначальной идеи прыжков становится возможным?

Используя этот подход, я наконец решил проблему.