Автор задачи: Егор Юлин, разработчик: Даниил Орешников
К ответу можно было прийти, сначала придумав достаточно наивное решение. Оно заключается в том, чтобы выписать $$$n$$$ побитово в двоичной системе счисления, дописывая перед каждым битом $$$0$$$, а в конце дописав бит $$$1$$$. Тогда при восстановлении числа достаточно найти первую единицу на четной позиции, обрезать полученную строку $$$q$$$ по ней, и перевести левую часть из двоичной системы в десятичную.
Однако такое решение требует от строки $$$s$$$ быть длины $$$2 \log_2 n + 1$$$. Альтернативный способ — закодировать число так, чтобы в его коде какая-то последовательность бит гарантированно не встречалась, и завершить код этой последовательностью. Тогда процесс слабо отличается от описанного выше.
Основная идейная сложность этой задачи — это понять, при чем тут $$$\sqrt{2}$$$. Правильный ответ — ни при чем, кроме того, что значения $$$\sqrt{2}$$$ и $$$\frac{1}{\log_2 \phi}$$$ очень близки друг к другу ($$$\approx 1.41$$$ и $$$\approx 1.44$$$). Здесь за $$$\phi$$$ обозначено золотое сечение — решение уравнения $$$x^2 - x - 1 = 0$$$.
Поэтому значение $$$\sqrt{2} \log_2 n$$$ достаточно близко к значению $$$\log_\phi n$$$, особенно учитывая, что при $$$n \leqslant 10^{18}$$$, $$$\log_\phi n < 90$$$.
А этот вывод (либо дальнейшие рассуждения от наивного решения, что нам хочется гарантировать отсутствие какой-то последовательности бит в коде) уже должен натолкнуть на фибоначчиеву систему счисления. Ее полезное свойство в том, что в ней никогда не встречаются два единичных бита подряд.
Таким образом:
В ограничениях данной задачи такой метод позволял уложиться в ограничение на длину строки, так как числа Фибоначчи растут со скоростью $$$F_n \approx \phi^n$$$, а поправка на разницу между $$$\sqrt{2} \log_2 n$$$ и $$$\log_\phi n$$$ не превосходит $$$2$$$.