Очень классная задача на динамическое программирование, в которой надо ещё придумать, как быстро посчитать результат. Читаем условие:
Идея динамического программирования лежит на поверхности - чтобы вычислить стоимость для N надо знать стоимость для S и N - S (и правильно распределить, к чему прибавить 1, а к чему - 2).
Получаем одномерную динамику - ответ зависит лишь от количества элементов в множестве. База динамики: для 1 ответ 0. Если загаданное число среди одного, то не надо задавать вопросов, чтобы узнать, что это за число.
Шаг динамики: проверить все разбиения числа N на два натуральных слагаемых и выбрать оптимальное. Для примера получается такая таблица:
Давайте посмотрим, как для 8 получается ответ. Есть четыре варианта получения девятки: 1 + 7, 2 + 6, 3 + 5, 4 + 4. Очевидно, что меньшее множество надо помещать в S, чтобы двойка добавлялась к меньшему числу, чтобы не ухудшать худший случай. Тогда получается:
- 1 + 7: max(0 + 2, 5 + 1) = 6
- 2 + 6: max(2 + 2, 5 + 1) = 6
- 3 + 5: max(3 + 2, 4 + 1) = 5
- 4 + 4: max(4 + 2, 4 + 1) = 6
Оптимальное разбиение - 3 + 5 - с ответом 5 конфет.
Однако такое решение будет квадратично по времени работы. Что можно с этим делать:
- понять, что крайние случаи не будут подходить, поэтому проверять варианты с середины и прерывать проверку, когда становится хуже, чем найденный ранее ответ
- запоминать, где происходят изменения стоимости (а таких отсечек будет очень мало) и перепрыгивать сразу к ним
А можно написать простое решение, сгенерировать чуть больше ответов и методом пристального вглядывания увидеть закономерность: двойка встречается 1 раз, тройка - тоже 1, четвёрка - 2 раза, пятёрка - 3 раза, шестёрка - 5 раз, семёрка - 8.
Это ничто иное, как числа Фибоначчи. Мы уже разбирали как минимум две задачи про них (Задача 147. Числа Фибоначчи и Задача 271. Числа Фибоначчи - 2) и знаем, что они растут очень быстро. В этой задаче нам нужна сумма чисел Фибоначчи, то есть её рост будет ещё больше. А точнее, нам нужно минимальное число Фибоначчи, при котором сумма до него будет не меньше заданного N. То есть почти как в Задача 271. Числа Фибоначчи - 2, только сумма.
Считываем входные данные и приводим к числовому типу:
Случай с единичкой рассмотрим отдельно, поэтому инициализация первых чисел Фибоначчи будет, начиная со второго:
Каждое следующее будет вычислять в цикле уже знакомым выражением:
Но помимо самих чисел нам надо поддерживать их сумму и номер текущего числа, чтобы знать момент остановки и ответ соответственно:
Теперь осталось вывести ответ:
Здесь мы сразу обрабатываем случай с единичкой:
- если n - 1 == 0, то операция and возвращает это значение (то есть 0),
- иначе - операция and возвращает второй операнд (то есть c).
Таким образом получили решение за логарифмическое время.
Предыдущий выпуск: Задача 16. Лесенка
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.