Задача B. Сломанный арифмометр с нетривиальным принципом работы

Автор:И. Олейников   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Один из известных коллекционеров недавно приобрел на аукционе старый арифмометр.

Арифмометр состоит из двух циферблатов, набора кнопок, которые можно нажать, и ручек, которые можно крутить. На первом циферблате показывается число от 0000 до 9999. К сожалению, арифмометр длительное время не ремонтировали, поэтому работают только кнопка, увеличивающая значение числа на 1, и ручка, за один поворот которой можно увеличить на 1 группу одинаковых разрядов числа из одного или более штук. Если в числе несколько групп одинаковых разрядов, то имеется возможность выбрать любую. Например, возможна следующая последовательность действий 1234 ↦ 1244 ↦ 2244 ↦ 3344 ↦ 4444 ↦ 4445 ↦ 5555. На втором циферблате отображается набранная сумма с учетом знака. При этом число на втором циферблате меняется согласно следующим правилам:

  1. Одно нажатие на кнопку или один поворот ручки считается одним действием.
  2. Если число произведенных действий нечетно, то к числу на втором циферблате будет прибавлен результат действия на первом.
  3. Если число произведенных действий четно, то от числа на втором циферблате отнимается результат действия на первом.
В начальном состоянии на первом циферблате установлено число A, а на втором — 0.

Например: если A = 1234, то после нажатия кнопки на обоих циферблатах будет установлено число 1235. После еще одного нажатия кнопки на первом циферблате будет 1236, а на втором — 1.

Коллекционер хочет узнать, какое наименьшее число он сможет установить на втором циферблате, произведя ровно K действий.

Формат входного файла

Во входном файле содержаться два числа A и K.

Формат выходного файла

Выходной файл должен содержать единственное число — минимальное число на втором циферблате после K действий.

Ограничения

0000 ≤ A ≤ 9999, 0 ≤ K ≤ 10

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1130 4
-2220
2
0023 1
24
3
1234 0
0

Разбор

Данная задача была задумана как переборная в противовес динамическому программированию в задаче "Сломанный арифмометр".

Эталонное решение использует рекурсивную процедуру, в которую передается номер текущего действия и числа на обоих циферблатах. Эта процедура проделывает все возможные одношаговые действия с числом на первом циферблате и затем рекурсивно вызывает себя, увеличивая номер шага и переписывая числа на циферблатах согласно правилам 2 и 3. Когда номер шага превышает K число на втором циферблате сравнивается с текущим значением глобальной переменной-минимума (ms). Затем происходит выход на предыдущий шаг рекурсии. После окончания процедуры в переменной ms будет содержаться ответ.


0.131s 0.010s 13