Лиза Божья Коровка
Лиза Божья Коровка обожает математику. Каждый день она несколько раз пересчитывает свои семь точек. Чтобы ещё больше развить свои навыки, она учится в Колледже Членистоногих на Лугу. Сегодня она готовится к экзамену у профессора Калькулона Сороконожки. На экзамене студент должен ввести количество ног Калькулона на дисплее калькулятора. Этот калькулятор был найден много лет назад среди другого мусора на свалке. Некоторые его клавиши не работают, и дисплей может отображать только три цифры. Рабочие клавиши образуют подмножество:
0 1 2 3 4 5 6 7 8 9 + − / =
Кнопки "0", "1", ..., "9" называются цифровыми кнопками, "=" — это кнопка равенства, а остальные кнопки — это операторные кнопки. У калькулятора также есть клавиша "C" для сброса, но только Калькулон может её нажимать, поэтому мы не будем рассматривать её в этой задаче. Результат экзамена зависит от количества нажатий клавиш для получения заданного значения. Лиза хочет добиться идеального результата, поэтому ей нужно найти кратчайшую возможную последовательность нажатий клавиш.
Работа калькулятора описана на диаграмме ниже. Калькулятор имеет три регистра: disp хранит отображаемое значение, operator — последний нажатый оператор или кнопка равенства, а value — это сохранённое значение. В начале экзамена калькулятор находится в состоянии S, и регистры имеют значения, установленные блоком INIT. Нажатие кнопки B изменяет состояние в направлении стрелки, помеченной B, и выполняется код в блоке рядом со стрелкой. Результат функции eval(val_1, op, val_2) — это результат применения оператора к val_1 и val_2, то есть, например, val_1 + val_2.
Описание может показаться сложным, но калькулятор работает вполне стандартно. Есть лишь несколько особенностей и деталей, на которые следует обратить внимание:
Он отображает только неотрицательные целые числа в диапазоне [0, 999]. Получение значения вне этого диапазона в любое время во время экзамена вызывает ошибку и провал на экзамене.
Результат деления — это целое число; точный результат всегда округляется вниз.
Нажатие кнопки равенства два или более раз всегда имеет тот же эффект, что и нажатие её один раз.
Нажатие кнопки равенства сразу после кнопки оператора приводит к тому, что оператор оценивается с двумя равными операндами.
Последовательность кнопок операторов ведёт себя так же, как если бы была нажата только последняя кнопка последовательности.
Например, в первом примере входных данных, 2 2 / 3 + и 2 2 / 3 / являются оптимальными решениями, в то время как 3 + 2 + 2 + также является решением, но более длинным. Во втором примере входных данных, 3 + 2 + 2 + и 2 + = + 3 + являются оптимальными решениями.
Входные данные
Каждая строка входных данных описывает один тестовый случай. Строка начинается с непустого списка доступных кнопок (из разрешённого набора), за которым следует один пробел и число N (0 ≤ N ≤ 999), обозначающее количество ног Калькулона, то есть число, которое должно быть отображено.
Выходные данные
Для каждого тестового случая выведите одну строку с длиной кратчайшей последовательности кнопок, нажатие которых приведёт к отображению числа N на калькуляторе. Если задачу невозможно решить, напишите строку со словом "impossible".