首页 > 代码库 > codeforces 58E：Expression
codeforces 58E：Expression
Description
One day Vasya was solving arithmetical problems. He wrote down an expression a + b = c in his notebook. When the teacher checked Vasya‘s work it turned out that Vasya had solved the problem incorrectly. Now Vasya tries to find excuses. He says that he simply forgot to write down several digits in numbers a, b and c, but he can‘t remember what numbers they actually were. Help Vasya, find such numbers x, y and z, with which the following conditions are met:
x + y = z,
from the expression x + y = z several digits can be erased in such a way that the result will be a + b = c,
the expression x + y = z should have the minimal length.
Input
The first and only input line contains the expression a + b = c (1 ≤ a, b, c ≤ 106, a, b and c don‘t contain leading zeroes) which is the expression Vasya wrote down.
Output
Print the correct expression x + y = z (x, y and z are non-negative numbers without leading zeroes). The expression a + b = c must be met in x + y = z as a subsequence. The printed solution should have the minimal possible number of characters. If there are several such solutions, you can print any of them.
Examples
Input
2+4=5
Output
21+4=25
Input
1+1=3
Output
1+31=32
Input
1+1=2
Output
1+1=2
正解：搜索
解题报告：
今天考试T6，9道题里面唯一一道没动的，开始以为是E题就会很难...
简单思路就是搜索，每次看一下当前的个位是否相等，如果相等，那么显然可以约掉这个已经相等的个位并只处理高位，当然记得进位；否则，我们考虑a、b、c三个元素，保持两个不变，我们把第三个增加一位使得末位与另外两位对应，然后其余部分直接往前推一位，也就是×10。直到c=0，那么肯定只需要把c的最高位补一个a+b剩下的数就可以了，算一下位数。当然要加一个最优性剪枝。
1 //It is made by jump~ 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <algorithm> 8 #include <ctime> 9 #include <vector>10 #include <queue>11 #include <map>12 #include <set>13 using namespace std;14 typedef long long LL;15 int ans,ansa,ansb;16 LL mi[19];17 18 inline int getint()19 {20 int w=0,q=0; char c=getchar();21 while((c<‘0‘ || c>‘9‘) && c!=‘-‘) c=getchar(); if(c==‘-‘) q=1,c=getchar(); 22 while (c>=‘0‘ && c<=‘9‘) w=w*10+c-‘0‘, c=getchar(); return q ? -w : w;23 }24 25 inline void dfs(LL a,LL b,LL c,LL nowa,LL nowb,LL jin,int nowl,int wei){26 if(nowl>=ans) return ; 27 if(a==0&&b==0&&c==0&&jin==0) { ans=nowl; ansa=nowa; ansb=nowb; return ; }28 if(c==0) {29 int tot=0; LL lin=a+b+jin; while(lin) tot++,lin/=10;//全部加给c30 dfs(0,0,0,nowa+a*mi[wei],nowb+b*mi[wei],0,nowl+tot,wei);31 return;32 }33 if((a+b+jin)%10==c%10) dfs(a/10,b/10,c/10,nowa+a%10*mi[wei],nowb+b%10*mi[wei],(a%10+b%10+jin)/10,nowl,wei+1);//去掉已经相等的低位部分，记得给公共的低位部分进位34 else{35 dfs(a*10+(c+10-b%10-jin)%10,b,c,nowa,nowb,jin,nowl+1,wei);//a后面加一位与前两个数还有进位的和的个位部分36 dfs(a,b*10+(c+10-a%10-jin)%10,c,nowa,nowb,jin,nowl+1,wei);//b后面加一位与前两个数还有进位的和的个位部分37 dfs(a,b,c*10+(a+b+jin)%10,nowa,nowb,jin,nowl+1,wei);///c后面加一位与前两个数还有进位的和的个位部分38 }39 }40 41 inline void work(){42 int a,b,c; scanf("%d+%d=%d",&a,&b,&c);43 ans=12; mi[0]=1; for(int i=1;i<=18;i++) mi[i]=mi[i-1]*10;44 dfs(a,b,c,0,0,0,0,0);45 printf("%d+%d=%d",ansa,ansb,ansa+ansb);46 }47 48 int main()49 {50 work();51 return 0;52 }
codeforces 58E：Expression