Дима работает на складе чисел. Он входит на склад с двоичным числом $$$x=0$$$. Ему необходимо превратить свое число $$$x$$$ в число $$$s$$$. Для этого на складе есть два автомата для увеличения чисел.
Первый автомат увеличивает двоичное число $$$x$$$ на $$$1$$$ за $$$a$$$ секунд. Он расположен слева от входа на склад, в $$$p$$$ секундах ходьбы от входа.
Второй автомат умножает двоичное число $$$x$$$ на $$$2$$$ за $$$b$$$ секунд. Он расположен справа от входа на склад, в $$$q$$$ секундах ходьбы от входа.
Таким образом, если Диме понадобится дойти от одного автомата до другого, он потратит $$$p+q$$$ секунд. Исходно он находится у входа на склад.
Помогите Диме узнать, за какое наименьшее количество секунд можно получить число $$$x=s$$$ и вернуться ко входу на склад.
Число в двоичной системе счисления из $$$n$$$ цифр, представимое в виде: $$$\overline{a_1 a_2 \ldots a_n}$$$ $$$(a_i \in \{0, 1\})$$$, равно $$$2^{n-1} \cdot a_1 + 2^{n-2} \cdot a_2 + \ldots + 2 \cdot a_{n-1} + a_n$$$. ($$$a_1 = 1$$$ при $$$n > 1$$$, то есть число не имеет ведущих нулей).
В первой строке даны два целых числа $$$a$$$ и $$$b$$$ в десятичной записи $$$(1 \le a, b \le 10^9)$$$ — время, которое потребуется автоматам для увеличения числа.
Во второй строке даны целые числа $$$p$$$ и $$$q$$$ в десятичной записи $$$(0 \le p, q \le 10^9)$$$ — расстояние от входа на склад до первого и второго автоматов.
В третьей строке дано число $$$s$$$ в двоичной системе счисления без ведущих нулей (кроме случая $$$s = 0$$$). Длина числа $$$s$$$ не превышает $$$100\,000$$$ цифр.
Выведите минимальное количество секунд, которое потребуется, чтобы из $$$x=0$$$ получить $$$x=s$$$, пользуясь автоматами, и вернуться ко входу на склад.
Задача состоит из 25 тестов, не считая тестов из условия. Каждый тест оценивается независимо в 4 балла. Все тесты можно разделить на следующие группы:
Номер | Макс. балл | Доп. ограничения |
$$$1$$$ | $$$20$$$ | Размер $$$s$$$ не больше 5 |
$$$2$$$ | $$$20$$$ | Размер $$$s$$$ не больше 20 |
$$$3$$$ | $$$20$$$ | $$$p=q=0$$$ |
$$$4$$$ | $$$20$$$ | Размер $$$s$$$ не больше $$$1000$$$ |
$$$5$$$ | $$$20$$$ | Размер $$$s$$$ не больше $$$100\,000$$$ |
1 22 3101011
28
10 2030 400
0
В первом тесте необходимо получить число $$$s=32 + 8 + 2 + 1 = 43$$$ в десятичной записи.
Оптимальная последовательность действий: Дима идет к первому автомату (2 секунды), прибавляет к числу единицу 5 раз (5 секунд), потом идет ко второму автомату ($$$2+3=5$$$ секунд), умножает число 3 раза ($$$3 \cdot 2 = 6$$$ секунд) и получает число 40, возвращается к первому автомату ($$$3+2=5$$$ секунд), прибавляет единицу 3 раза (3 секунды), и идет ко входу на склад (2 секунды). Всего потрачено 28 секунд.
Во втором тесте у Димы с самого начала есть число $$$x=0$$$.