Просмотр кода страницы ACMP 644

== Ссылка на задачу ==
* [http://acmp.ru/?main=task&id_task=644 ACMP #644 &mdash; Временной ключ-2]

== Комментарии ==
Максимальный ответ в задаче не превышает 2^37. Следовательно, можно считать, что соседние элементы ряда с любым начальным N отличаются не более чем на 37.

Обозначим за R ряд, начинающийся с N = 1: R = { 1, 2, 3, 5, 7, 10, ... }.

Заметим, что ряд, начинающийся с произвольного N, рано или поздно начинает повторять ряд R. Это замечание наводит на идею сведения задачи для произвольного N к задаче для N = 1. Пусть мы умеем: 
* определять, входит ли заданное число в ряд R; 
* по элементу ряда R вычислять его индекс; 
* по индексу вычислять элемент ряда R.
Тогда решение задачи для произвольных N и K таково: 
* пока N не входит в ряд R и K > 0, выполняем N += S(N), K--;
* если K = 0, то ответ &mdash; N;
* иначе вычисляем индекс I числа N в ряду R; ответ &mdash; элемент R с индексом (I + K).

Пусть имеется функция index(X), возвращающая индекс числа X, если оно входит в ряд R, либо -1 в противном случае. Тогда определение того, входит ли X в ряд R, сводится к проверке index(X) &ne; -1. Вычисление элемента по заданному индексу можно осуществить при помощи двоичного поиска (для этого понадобится вспомогательная функция, возвращающая для элементов, не входящих в R, индекс первого меньшего элемента R; такую функцию можно реализовать простым перебором, уменьшая X до подходящего значения: как показано выше, потребуется не более 37 итераций).

Как вычислить index(X)? Требуется предпосчитать следующие значения:
* iterations[from][add1][power] &mdash; количество итераций, требуемых для получения из числа from числа, не меньшего 2^power; при этом на каждой итерации дополнительно учитывается add1 единиц;
* result[from][add1][power] &mdash; число, получающееся в результате выполнения описанных выше итераций.
При помощи данных значений можно восстановить общее число итераций для получения числа X из 1, суммируя количества итераций для получения значащих двоичных единиц от старших разрядов к младшим.
from, add1 и power находятся в диапазоне от 0 до 37 - 1. Для ускорения предпосчёта следует заметить, что iterations[from][add1][power] часто тривиально выводятся из iterations[from - 1][add1][power].

Предпосчитанный массив нельзя целиком сохранить в коде решения из-за его размера, поэтому следует сохранить только части (from = 0) и (from = 1, add1 = 0). Восстановление остальных частей по данным производится достаточно быстро (с использованием указанного выше соображения).

[[Category: Сборник задач: ACMP]]
[[Category: Задачи: Прекалк]]
[[Category: Задачи: Жёсткие ограничения]]
[[Category: Задачи: Битовая арифметика]]