Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1523. Вычислительная машина
Поиск в ширину (BFS)Олимпиадные задачи на русском языке
| 09/12/2010 | Сборы: Общий итог (4G) |
| 30/12/2010 | Сборы 4: Домашнее задание (E) |
| 26/11/2013 | Занятие 10 для начинающих (D) |
Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (1)
Программист Петя сконструировал свою вычислительную машину. Она могла хранить в
памяти любое неотрицательное целое число. Также она могла выполнять несколько
элементарных арифметических операций (сложение, вычитание, умножение, деление),
в которых в качестве обоих аргументов выступало число, хранящееся в памяти машины.
Результат выполнения операции записывался в память машины вместо имеющегося там
числа. Таким образом, операция "+" удваивает хранящееся в памяти число,
операция "-" обнуляет это число, операция "*" возводит это число в
квадрат, операция "/" превращает это число в 1.
Однажды Петя задумался: а за какое наименьшее количество арифметических операций
он может получить с помощью своей машины число `B`, если изначально в памяти машины
хранилось число `A`? Помогите Пете разработать программу, отвечающую на поставленный
вопрос.
Ввод
В первой строке входного файла записаны два целых числа `A` и `B`, разделенные одним пробелом.
(`1\ ≤\ A,\ B\ ≤\ 1\ 000\ 000\ 000`).
Вывод
В первой строке выходного файла выведите последовательность арифметических операций,
позволяющую получить число `B` из числа `A` (см. примеры). Последовательность должна содержать
наименьшее возможное количество операций. В случае, если существует несколько таких
последовательностей одинаковой длины, нужно выдать лексикографически минимальную в соответствии
с ASCII кодами символов арифметических операций. Арифметические операции (+, -, *, /) по возрастанию
ASCII кодов идут в следующем порядке: *, +, -, /.
В случае, если невозможно получить число `B` из числа `A`, необходимо вывести строку ":-(" (без кавычек).
Примечания:
- последовательность операций может быть пустой, в таком случае вывод должен содержать переход на новую строку (см. примеры);
- делить на 0 нельзя.
Пример ввода 1
7 392
Пример вывода 1
+*+
Пример ввода 2
7 7
Пример вывода 2
Пример ввода 3
7 9
Пример вывода 3
:-(
Пример ввода 4
10 1
Пример вывода 4
/
