Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1794. Бактерии
Сокращение перебора с помощью идеиОлимпиадные задачи на русском языке
| 25/06/2012 | Лето 2012 - дорешивание ( 9A) |
| 09/07/2012 | Лето 2012 - 9 (A) |
Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
У юного биолога Антона в красивой стеклянной колбе живут `n` бактерий.
Добавляя различные реактивы в колбу, Антон может контролировать число бактерий.
Так, если `p` – некоторое простое число, то Антон умеет в домашних условиях
получать вещество `C_p\ H_{2p+1}\ "OH"`, которое, будучи добавленным в колбу,
уменьшает число бактерий ровно в `p` раз. Если же число бактерий не делилось на `p`,
то результат действия вещества неопределен, и эксперимент теряет научную точность.
Этого Антон допустить не желает, поэтому он применяет вещество `C_p\ H_{2p+1}\ "OH"` только
когда число бактерий делится на `p`.
Кроме того, у Антона на кухне есть неограниченный запас диэтиламида лизергиновой кислоты (`C_20\ H_25\ N_3\ O`).
При добавлении в колбу с бактериями диэтиламида лизергиновой кислоты, число бактерий возводится
в квадрат.
Антон хочет, чтобы в колбе стало `m` бактерий.
При этом он хочет добавлять какие-либо вещества в колбу наименьшее возможное число раз.
Помогите ему сделать это.
Во входном файле содержатся два натуральных числа `n` и `m` (`1\ ≤\ n,\ m\ ≤\ 10^9`) – изначальное и желаемое число бактерий в колбе у Антона.
Если получить ровно `m` бактерий невозможно, выведите в выходной файл слово Impossible.
Если же искомый результат достижим, выведите кратчайшую последовательность добавлений веществ,
которая позволяет его достичь, в следующем формате:
добавление вещества `C_p\ H_{2p+1}\ "OH"` кодируется числом `p`, добавление вещества `C_20\ H_25\ N_3\ O` – числом 0.
Числа должны быть разделены пробелами и/или переводами строк.
Если существует несколько кратчайших последовательной добавлений веществ,
оставляющих `m` бактерий, выведите любую из них.
Пример ввода 1
12 18
Пример вывода 1
2 0 2
Пример ввода 2
56 6
Пример вывода 2
Impossible
В первом примере Антону требуется добавлять в колбу вещества три раза:
сначала добавить `C_2\ H_5\ "OH"`, уменьшая число бактерий в два раза, то есть оставляя 6 бактерий;
затем добавить `C_20\ H_25\ N_3\ O`, возводя число бактерий в квадрат, то есть увеличивая его до 36;
и наконец, добавить снова `C_2\ H_5\ "OH"`, деля число бактерий на два и делая его равным 18.
Источник: командный чемпионат школьников Санкт-Петербурга по программированию, 2010
