#P2702. Matchstick Equation Correction
Matchstick Equation Correction
Matchstick Equation Correction
You are given an equation consisting of digits and the operators +
, -
, and =
. In this puzzle you are allowed to move exactly one matchstick that forms a digit. You cannot move any matchstick that forms an operator; that is, the plus, minus, and equals signs remain unchanged. After the move the configuration of matchsticks composing every digit must exactly match the standard seven‐segment representation shown in Figure 2 (i.e. the digits 0 through 9).
If by moving one matchstick the equation can be made valid (i.e. the arithmetic expression holds true), output the new equation; otherwise, output No
.
The valid transformations are separated into two types:
- Self-move transformations (a single digit is modified by relocating one of its matchsticks within itself):
\(0\to6,\;0\to9\)
\(2\to3\)
\(3\to2,\;3\to5\)
\(5\to3\)
\(6\to0,\;6\to9\)
\(9\to0,\;9\to6\) - Cross-move transformations (one matchstick is removed from one digit and added to a different digit):
- Removal moves (donor digit loses a matchstick):
\(6\to5\), \(7\to1\), \(8\to6,\;8\to0,\;8\to9\), \(9\to5,\;9\to3\) - Addition moves (receiver digit gains a matchstick):
\(0\to8\), \(1\to7\), \(3\to9\), \(5\to9,\;5\to6\), \(6\to8\), \(9\to8\)
- Removal moves (donor digit loses a matchstick):
You may apply either a self-move or a cross-move (which involves two digits) to attempt to correct the equation.
inputFormat
The input consists of a single line containing an equation in the format A+B=C or A-B=C, where A, B, and C are non-negative integers that may have multiple digits. The line contains only digits and the symbols +
, -
, and =
.
outputFormat
If it is possible to obtain a valid equation by moving exactly one matchstick as described, output the corrected equation. Otherwise, output No
.
sample
2+5=8
3+5=8