Автор: | И. Олейников | Ограничение времени: | 2 сек | |
Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
Выходной файл: | output.txt | |||
Максимальный балл: | 100 |
Один из известных коллекционеров недавно приобрел на аукционе старый арифмометр.
Арифмометр состоит из двух циферблатов, набора кнопок, которые можно нажать, и ручек, которые можно крутить. На первом циферблате показывается число от 0000 до 9999. К сожалению, арифмометр длительное время не ремонтировали, поэтому работают только кнопка, увеличивающая значение числа на 1, и ручка, за один поворот которой можно увеличить на 1 группу одинаковых разрядов числа из одного или более штук. Если в числе несколько групп одинаковых разрядов, то имеется возможность выбрать любую. Например, возможна следующая последовательность действий 1234 ↦ 1244 ↦ 2244 ↦ 3344 ↦ 4444 ↦ 4445 ↦ 5555. На втором циферблате отображается набранная сумма с учетом знака. При этом число на втором циферблате меняется согласно следующим правилам:
Например: если A = 1234, то после нажатия кнопки на обоих циферблатах будет установлено число 1235. После еще одного нажатия кнопки на первом циферблате будет 1236, а на втором — − 1.
Коллекционер хочет узнать, какое наименьшее число он сможет установить на втором циферблате, произведя ровно K действий.
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|
Данная задача была задумана как переборная в противовес динамическому программированию в задаче "Сломанный арифмометр".
Эталонное решение использует рекурсивную процедуру, в которую передается номер текущего действия и числа на обоих циферблатах. Эта процедура проделывает все возможные одношаговые действия с числом на первом циферблате и затем рекурсивно вызывает себя, увеличивая номер шага и переписывая числа на циферблатах согласно правилам 2 и 3. Когда номер шага превышает K число на втором циферблате сравнивается с текущим значением глобальной переменной-минимума (ms). Затем происходит выход на предыдущий шаг рекурсии. После окончания процедуры в переменной ms будет содержаться ответ.