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). Восстановление остальных частей по данным производится достаточно быстро (с использованием указанного выше соображения).