ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Open Personal Contest 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Delights of Pipe-weed

Time limit: 1.0 second
Memory limit: 64 MB
The pipe-weed of Shire is famous for its befuddling effect. But you don't know probably that hobbits use it to educate their offsprings. They roll pipe-weed into sticks and let children play with them. A child may even study arithmetics if the parents make digits and signs of operations using such sticks. The plus sign is obtained by putting a stick over another stick crosswise and the sign of equality is two parallel sticks. The picture shows how to make digits from 0 to 9 using pipe-weed sticks.
Problem illustration
Little hobbits spend half of their education time to learn the addition, so we couldn't obtain information about how to make other signs of operations.
Sam once told that as a child he had liked to make fun of his father by moving sticks in an equality in such a way that it had become invalid. And now Sam invented a new entertainment for his own children. He arranges sticks on a table so that they make up an arithmetic equality of the form X + Y = Z and asks the children to make it valid by moving no more than K sticks. Each of the numbers X, Y and Z must have less than 9 digits and must not have any leading zeroes (but it can be equal to zero). It is forbidden to change the number of signs and digits as well as throw out sticks or add new sticks. Help Sam to determine if his problem can be solved.


The first line contains an expression of the form a1 + a2 = b (0 ≤ a1a2b < 108). The second line contains the integer K (0 ≤ K ≤ 100).


If it is possible to make the expression valid by moving no more than K sticks, then output one of the valid expressions that can be obtained this way. Otherwise, output «Impossible».


Problem Author: Sergey Pupyrev
Problem Source: VIII USU Open Personal Contest (March 3, 2007)
To submit the solution for this problem go to the Problem set: 1536. Delights of Pipe-weed