Hide

Problem F
Lisa the Ladybug

/problems/ladybug/file/statement/en/img-0001.png
Lisa the Ladybug likes mathematics. She counts her seven dots several times every day. To further improve her skills, she studies at the Arthropoda College in the Meadow. Today, she is preparing for an exam by her professor, Calculon the Centipede. At the exam, the student is expected to show the number of Calculon’s legs on the display of a calculator. The calculator was found many years ago among other waste in a landfill. Some of its keys are not working and the display has only three digits. The working keys form a subset of: \[ \tt 0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ +\ -\ *\ /\ = \]

Buttons 0,1,…, 9 are called the numeric buttons, = is the equals button, and the other buttons are the operator buttons. The calculator also has the C key to reset it, but only Calculon is allowed to press it, so we will not consider it in this problem. The result of the exam depends on the number of keys pressed to obtain the prescribed value. Lisa wants a perfect score and so she needs to find the shortest possible sequence of key presses.

The work of the calculator is described by the diagram below. The calculator has three registers: disp holds the value displayed, operator is the last operator or equals button pressed and value is a stored value. At the beginning of the exam, the calculator is in the state $S$ and the registers have the values set by the INIT block. Pressing a button $B$ changes the state in the direction of the arrow labeled by $B$ and the code in the block next to the arrow is executed. The result of the function $eval(val_1, op, val_2)$ is the result of the operator applied on $val_1$ and $val_2$, that is, for example, $val_1 + val_2$.

\includegraphics[width=0.8\textwidth ]{automaton}

The description may look complicated, but the calculator works in quite a standard way. There are just a few specifics and details that you should take note of:

  • It displays only non-negative integers in the range $[0,999]$. Obtaining a value outside this range anytime during the exam causes an error and failure at the exam.

  • Result of a division is an integer; the exact result is always rounded down.

  • Pressing the equals button two or more times always has the same effect as pressing it once.

  • Pressing the equals button right after an operator button results in the operator being evaluated with two equal operands.

  • A sequence of operator buttons behaves in the same way as if only the last button of the sequence was pressed.

For example, in the first sample input, $2\ 2\ /\ 3\ +$ and $2\ 2\ /\ 3\ /$ are among the optimal solutions, while $3\ +\ 2\ +\ 2\ +$ is also a solution, but longer. In the second sample input, $3\ +\ 2\ +\ 2\ +$ and $2\ +\ =\ +\ 3\ +$ are among the optimal solutions.

Input

Each line of the input describes one test case. A line starts with a non-empty list of available buttons (from the allowed set) followed by a single space and the number $N$ ($0 \le N \le 999$) denoting the number of Calculon’s legs, that means the number to be displayed.

There will be at most $250$ lines in the input.

Output

For each test case, output a single line with the length of the shortest sequence of buttons, the pressing of which will result in the number $N$ being displayed by the calculator. If the task cannot be solved, write a line with the word impossible.

Sample Input 1 Sample Output 1
23+/ 7
32=+ 7
3+= 6
3+= 9
2 0
1+ 11
2+* 1
1+ 17
1+= 17
5
6
3
6
0
2
impossible
15
11

Please log in to submit a solution to this problem

Log in