| Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 1 сек | |
| Входной файл: | calc.in | Ограничение памяти: | 256 Мб | |
| Выходной файл: | calc.out | |||
| Максимальный балл: | 100 |
В качестве домашнего задания по информатике ученикам предложено разработать специальный калькулятор, который устроен следующим образом.
Сначала пользователь вводит целое положительное число n, которое выводится на экран. Затем пользователь может нажимать на три кнопки: A, B и C.
При нажатии на кнопку A число, которое выведено на экран, делится на 2. Если число на экране нечетное, то остаток отбрасывается. Например, результат этой операции для числа 80 равен 40, а для числа 239 равен 119.
При нажатии на кнопку B к числу, которое выведено на экран, прибавляется 1, и результат делится на 2. Остаток от деления отбрасывается. Например, результат операции для числа 80 равен 40, а для числа 239 равен 120.
При нажатии на кнопку C происходит следующее. Если число, которое выведено на экран, положительное, то из него вычитается 1 и результат делится на 2, остаток отбрасывается. Если же перед нажатием на кнопку C на экран было выведено число 0, то оно остается неизменным. Например, результат операции для числа 80 равен 39, а для числа 239 равен 119.
Пользователь ввел число n и собирается нажать на кнопки операций в некотором порядке. В частности, он планирует нажать на кнопку A суммарно a раз, на кнопку B — b раз и на кнопку C — c раз. Его заинтересовал вопрос, какое минимальное число может получиться в результате выполнения описанных операций.
Требуется написать программу, которая по введенному числу n и числам a, b и c, показывающим количество произведенных на калькуляторе операций разного типа, определяет минимальное число, которое может получиться в результате работы калькулятора.
Входной файл содержит четыре целых числа: n, a, b и c. Числа заданы на одной строке, соседние числа разделены одним пробелом.
Требуется вывести одно число — минимальное число, которое может получиться у пользователя в результате работы калькулятора.
1 ≤ n ≤ 1018, 0 ≤ a, b, c ≤ 60
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | |
|---|---|---|---|---|
| n | Дополнительные ограничения на a, b, c | |||
| 1 | 26 | 1 ≤ n ≤ 109 | 0 ≤ (a + b + c) ≤ 7 | |
| 2 | 23 | 1 ≤ n ≤ 1018 | c = 0 | |
| 3 | 24 | 1 ≤ n ≤ 1018 | b = 0 | |
| 4 | 27 | 1 ≤ n ≤ 1018 | 1, 2, 3 | |
По запросу сообщается результат окончательной проверки на каждом тесте.
В примере пользователю необходимо оптимально действовать следующим образом: нажать на кнопку B и получить число 36, затем нажать на кнопку A и получить число 18, затем нажать на кнопку C и получить число 8, затем второй раз нажать на кнопку A и получить число 4.
| № | Входной файл (calc.in) |
Выходной файл (calc.out) |
|---|---|---|
| 1 |
|
|