ACMP 644
Ссылка на задачу
Комментарии
Максимальный ответ в задаче не превышает 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, то ответ — N;
- иначе вычисляем индекс I числа N в ряду R; ответ — элемент R с индексом (I + K).
Пусть имеется функция index(X), возвращающая индекс числа X, если оно входит в ряд R, либо -1 в противном случае. Тогда определение того, входит ли X в ряд R, сводится к проверке index(X) ≠ -1. Вычисление элемента по заданному индексу можно осуществить при помощи двоичного поиска (для этого понадобится вспомогательная функция, возвращающая для элементов, не входящих в R, индекс первого меньшего элемента R; такую функцию можно реализовать простым перебором, уменьшая X до подходящего значения: как показано выше, потребуется не более 37 итераций).
Как вычислить index(X)? Требуется предпосчитать следующие значения:
- iterations[from][add1][power] — количество итераций, требуемых для получения из числа from числа, не меньшего 2^power; при этом на каждой итерации дополнительно учитывается add1 единиц;
- result[from][add1][power] — число, получающееся в результате выполнения описанных выше итераций.
При помощи данных значений можно восстановить общее число итераций для получения числа X из 1, суммируя количества итераций для получения значащих двоичных единиц от старших разрядов к младшим. from, add1 и power находятся в диапазоне от 0 до 37 - 1. Для ускорения предпосчёта следует заметить, что iterations[from][add1][power] часто тривиально выводятся из iterations[from - 1][add1][power].
Предпосчитанный массив нельзя целиком сохранить в коде решения из-за его размера, поэтому следует сохранить только части (from = 0) и (from = 1, add1 = 0). Восстановление остальных частей по данным производится достаточно быстро (с использованием указанного выше соображения).