Czech ACM Student Chapter

Czech Technical University in Prague

Charles University in Prague

Technical University of Ostrava

ˇ ´

Slovak University of Technology

Pavol Jozef Safarik University in Koˇice

s

ˇ

University of Zilina

Masaryk University

Matej Bel University in Bansk´ Bystrica

a

University of West Bohemia

CTU Open Contest 2012

Lisa the Ladybug

ladybug.c, ladybug.cpp, Ladybug.java

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:

0123456789 + - ∗ / =

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(val1 , op, val2 ) is the result of the operator applied on val1 and val2, that is,

for example, val1 + val2.

+-*/=

if(Button=='=' and operator ='=')

disp:=eval(value, operator, disp);

operator:=Button;

+-*/=

value:=disp;

O

operator:=Button

+-*/=

INIT

if(operator ∈ {'=', N/A})

/

disp:=0;

0-9

S

disp:=eval(value, operator, disp);

value:=0;

disp:=Button;

operator:=Button;

operator:=N/A;

value:=disp;

0-9

N

0-9

disp:=Button;

disp:=10*disp+Button;

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 Specification

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 ≤ N ≤ 999)

denoting the number of Calculon's legs, that means the number to be displayed.

Output Specification

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

Output for Sample Input

23+/ 7

5

32=+ 7

6

3+= 6

3

3+= 9

6

20

0

1+ 11

2

2+* 1

impossible

1+ 17

15

1+= 17

11