07/04/2025 06:42:38

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1794. Бактерии

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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

25/06/2012	Лето 2012 - дорешивание ( 9A)
09/07/2012	Лето 2012 - 9 (A)