Equations are not solvable in a general fashion. Here's an example.
It's not fair to solve unsolvable problems in the contest, so we would like you to solve a easier one. It's decidable in polynomial time, so it's fair.
Xiao Shi is given an equation of the form
A+B=CA + B = CA+B=C, where
AAA,
BBB and
CCC are positive integers. However, the equation may not be true at the moment. Xiao Shi can insert a single digit (
000-
999) anywhere in the equation, before or after any existing digit, to make it true.
For example, if the equation is
12+34=14612 + 34 = 14612+34=146, Xiao Shi can insert
111 to
121212 (either
1‾12\overline{1}12112 or
11‾21\overline{1}2112) to make it
112+34=146112 + 34 = 146112+34=146.
Xiao Fan's task is to determine if there exists a way to insert a digit in the equation to make it true, or it is already true. Can you help him?