#P2702. Matchstick Equation Correction

    ID: 15967 Type: Default 1000ms 256MiB

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\)

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