问题 K: 火柴棒等式3.0 时间限制: 1 Sec 内存限制: 128 MB
题目描述 给定一个由火柴棒组成的算式,问:是否能够移动一根火柴棒使算式成立。例如:5+7=7,可以通过移动一根火柴变成6+1=7。使等式成立,具体如 下图:
0~9十个数字的火柴棒形式如下,加号和等号未给出,原因随后会告诉选手。 现在简化问题,我们现在只需要解决形如 a+b = c 的火柴算式问题,其中加号和等号视为无法移动,也不能引入新的数学符号。也就是说,最终形成的答案也是 a’+b’=c’ 的形式。输入数据保证 a, b, c, 以及运算结果 a’ , b’, c’ 都是 0~99之间的数字。原算式及结果算式均不包含前导0(前导0没有火柴棒)。
输入 输入包含多组数据,每组数据一个算式,算式满足上述限制。
输出 对于每组测试样例,如果问题有解,也就是说输入等式可以通过移动一根火柴变成合法的等式,则输出两行,第一行为 “Yes”,接下来若干行为结果等式 a’ + b’ = c’,表示所有的解,输出解的顺序要求 a’ 升序。a’ 相同的情况满足 b’升序。 如果问题无解,则输出一行 “No” 如上面的例子 5+7=7 应输出 Yes 6+1=7
样例输入 10+3=12 15+27=54
样例输出 Yes 10+2=12 10+3=13 No
思路
穷举所有情况
注意的是 十位上不能有0 还有要去除等式本身成立的情况。
0 -> 6 , 9 ; 2 -> 3 ; 3 -> 2 , 5 ; 5 -> 3 ; 6 -> 0 , 9 ; 9 -> 0 , 6; 0 多 -> 8 ; 1 多 -> 7 ; 3 多 -> 9 ; 5 多 -> 6 , 9 ; 6 多 -> 8 ; 9 多 -> 8 ; 6 少 -> 5 ; 7 少 -> 1 ; 8 少 -> 0 , 6 , 9 ; 9 少 -> 3 , 5 ;
#include using namespace std;struct ANS {int a,b,c;char ch;}ans[100];char ch,no;int a,b,c,sign,A[6],tempA[6],N;bool cmp (ANS a , ANS b) {if (a.a < b.a) {return true ;} else if (a.a > b.a) {return false ;} else {return a.b < b.b ;}}void flag () {int I = tempA[0]*10 + tempA[1] ;int J = tempA[2]*10 + tempA[3] ;int K = tempA[4]*10 + tempA[5] ;if (I + sign*J == K) {if (I == a && J == b && K == c) {return ;}ans[N].a = I ;ans[N].b = J ;ans[N].c = K ;ans[N++].ch = ch ;}}bool is0 (int i) {if ((i == 0 || i == 2 || i == 4) && A[i] == 0) {return true ;}return false ;}void FLAG (int i) {if (A[i] == 6) {tempA[i] = 5 ;flag() ;}if (A[i] == 7) {tempA[i] = 1 ;flag() ;}if (A[i] == 8) {if (i != 0 && i != 2 && i != 4) {tempA[i] = 0 ;flag() ;}tempA[i] = 6 ;flag() ;tempA[i] = 9 ;flag() ;}if (A[i] == 9) {tempA[i] = 3 ;flag() ;tempA[i] = 5 ;flag() ;}tempA[i] = A[i] ;}void FLAG (int i , int j) {if (A[i] == 0) {tempA[i] = 8 ;FLAG(j) ;} else if (A[i] == 1) {tempA[i] = 7 ;FLAG(j) ;} else if (A[i] == 3) {tempA[i] = 9 ;FLAG(j) ;} else if (A[i] == 5) {tempA[i] = 6 ;FLAG(j) ;tempA[i] = 9 ;FLAG(j) ;} else if (A[i] == 6) {tempA[i] = 8 ;FLAG(j) ;} else if (A[i] == 9) {tempA[i] = 8 ;FLAG(j) ;}tempA[i] = A[i] ;}void self (int i) {if (A[i] == 0) {tempA[i] = 6 ;flag() ;tempA[i] = 9 ;flag() ;tempA[i] = 0 ;} else if (A[i] == 2) {tempA[i] = 3 ;flag() ;tempA[i] = 2 ;} else if (A[i] == 3) {tempA[i] = 2 ;flag() ;tempA[i] = 5 ;flag() ;tempA[i] = 3 ;} else if (A[i] == 5) {tempA[i] = 3 ;flag() ;tempA[i] = 5 ;} else if (A[i] == 6) {if (i != 0 && i != 2 && i != 4) {tempA[i] = 0 ;flag() ;}flag() ;tempA[i] = 9 ;flag() ;tempA[i] = 6 ;} else if (A[i] == 9) {if (i != 0 && i != 2 && i != 4) {tempA[i] = 0 ;flag() ;}tempA[i] = 6 ;flag() ;tempA[i] = 9 ;}tempA[i] = A[i] ;}int main(){while (cin >> a >> ch >> b >> no >> c) {N = 0 ;memset(ans,0,sizeof(ANS)*100);sign = ch == '+' ? 1 : -1 ;tempA[0] = A[0] = a/10 ;tempA[1] = A[1] = a%10 ;tempA[2] = A[2] = b/10 ;tempA[3] = A[3] = b%10 ;tempA[4] = A[4] = c/10 ;tempA[5] = A[5] = c%10 ;for (int i = 0 ; i < 6 ; i++) {if (i == 0 || i == 2 || i == 4) {if (A[i] == 0) {continue ;} else {self(i) ;}} else {self(i) ;}}for (int i = 0 ; i < 6 ; i++) {for (int j = 0 ; j < i ; j++) {if (is0(i)||is0(j)) {continue ;}FLAG(i,j);FLAG(j,i);}}if (N == 0) {printf("No\n");} else {printf("Yes\n");sort(ans,ans+N,cmp);for (int i = 0 ; i < N ; i++) {printf("%d%c%d=%d\n",ans[i].a,ans[i].ch,ans[i].b,ans[i].c);}}}return 0;}/*0 -> 6 , 9 ;2 -> 3 ;3 -> 2 , 5 ;5 -> 3 ;6 -> 0 , 9 ;9 -> 0 , 6;0 多 -> 8 ;1 多 -> 7 ;3 多 -> 9 ;5 多 -> 6 , 9 ;6 多 -> 8 ;9 多 -> 8 ;6 少 -> 5 ;7 少 -> 1 ;8 少 -> 0 , 6 , 9 ;9 少 -> 3 , 5 ;*/