Moving Sticks#1633
Here’s a simple puzzle: Move one stick in the figure below to make the equation correct.
Easy, right? Here’s the solution:
Write a program to solve similar puzzles knowing that:
Each puzzle consists of a left operand, an operator, a right operand, an equal sign, and a result. The two operands and the result are numbers, each made of one or more digits, and each less than 2^{31}.
The operator and the equal sign cannot be changed. You are only allowed to move sticks that form the digits.
You may not remove digits entirely or add any completely new digits. (i.e., you may only transform digits.)
Leading zeros are allowed in both input and output. Leading zeros in the output must be printed.
Each puzzle specifies the number of stick moves required. Your solution must move exactly as many sticks as specified. A stick may be moved at most once; it cannot be moved again. If a stick is moved, its original place must stay empty. (i.e., you cannot move another stick to that position.)
If a puzzle involves division, the division must be an exact integer division, i.e., without remainder.
Digits are "written" as follows:
Your program will be tested on one or more test cases. Each test case is specified on a single line in the following format:
A ⊙ B = R (n)
where A, B, and R are sequences of one or more digits, but no more than nine digits. ⊙ is one of four operators: + - * /. n is a natural number representing the number of sticks to move. One or more spaces separate A, ⊙, B, =, R, and (n).
The end of test cases is indicated by a separate line containing the word EOF (without the quotes).
For each puzzle, your program must print one line in the format:
k. result
Where k is the puzzle number (starting at 1), and result is the equation after solving the puzzle. The result must not include any spaces.
If there are multiple solutions, output only one. If the puzzle cannot be solved, print UNSOLVABLE (without the quotes) as the result.
Example 1