Moving Sticks
Time limit1sMemory limit128 MB
Given an arithmetic equation written in seven-segment digits, move exactly n segments so the equation becomes true, choosing the lexicographically smallest solution.
- Level
Hard8 of 10
- Topics
- Brute force, Implementation, Backtracking, Math
- Solved
- No attempts yet
Problem
Here is a simple puzzle. Move one stick in the figure below so that the equation becomes correct.

That one is easy. Here is the answer.

Write a program that solves puzzles of this kind under the rules below.
- A puzzle has a left operand, an operator, a right operand, an equal sign, and a result. The two operands and the result are numbers written with one or more digits, and each of them is smaller than .
- The operator and the equal sign never change. You may move only the sticks that form the digits.
- You can neither remove a digit nor add a new one, so every digit position holds a digit before and after the move.
- Leading zeros are allowed in the input and in the output, and a leading zero in the output must be printed.
- Each puzzle states how many sticks to move, and you must move exactly that many. A stick is moved at most once, and the place a stick came from stays empty, so no other stick may be put there.
- A division has to come out exactly, with no remainder.
- The digits are written with seven segments, as the figure below shows.

Input
The input has one or more puzzles. Each puzzle sits on one line in this format.
A ⊙ B = R (n)
A, B, and R are strings of one or more digits, and none of them is longer than nine digits. ⊙ is one of the four operators +, -, *, /. n is a natural number, the number of sticks that must be moved. One or more spaces separate A, ⊙, B, =, R, and (n).
A line that holds the word EOF, without quotes, ends the input.
Output
Print one line for each puzzle.
k.␣result
k is the puzzle number counted from 1, ␣ is one space, and result is the equation after the puzzle is solved. result carries no spaces. When a puzzle has more than one answer, print the one that comes first in lexicographic order: the smallest left operand, and among those the smallest right operand. When a puzzle has no answer, print UNSOLVABLE, without quotes, in place of result.