Advertisement
Morass

13170

May 27th, 2017
139
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.71 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define PB push_back
  4. #define ZERO (1e-10)
  5. #define INF int(1e9+1)
  6. #define CL(A,I) (memset(A,I,sizeof(A)))
  7. #define DEB printf("DEB!\n");
  8. #define D(X) cout<<"  "<<#X": "<<X<<endl;
  9. #define EQ(A,B) (A+ZERO>B&&A-ZERO<B)
  10. typedef long long ll;
  11. typedef pair<ll,ll> pll;
  12. typedef vector<int> vi;
  13. typedef pair<int,int> ii;
  14. typedef vector<ii> vii;
  15. #define IN(n) int n;scanf("%d",&n);
  16. #define FOR(i, m, n) for (int i(m); i < n; i++)
  17. #define F(n) FOR(i,0,n)
  18. #define FF(n) FOR(j,0,n)
  19. #define FT(m, n) FOR(k, m, n)
  20. #define aa first
  21. #define bb second
  22. void ga(int N,int *A){F(N)scanf("%d",A+i);}
  23. char s[666],r[666],m[666],c;
  24. int A,B,C,l,J[150],L,X,Y,Z;
  25. ll rd(char*s,int L){
  26.     ll S=0;
  27.     F(L)S*=10,S+=J[(int)s[i]];
  28.     return S;
  29. }
  30. void tf(char*s,int L){F(L)s[i]=J[(int)s[i]]+48;}
  31. int gt(int c){return c?J[c]:0;}
  32. //MULTIPLICATION
  33. bool mm(int I,int x,int b);
  34. bool rp(int I,int S,int t,int b){
  35.     if(t<=I){
  36.         int u=s[I-t],v=r[t];
  37.         int a=gt(u),c=gt(v);
  38.         if(~a){
  39.             if(~c)return rp(I,S+a*c,t+1,b);
  40.             F(10)if(!(b&1<<i)){
  41.                 J[v]=i;
  42.                 if(rp(I,S+i*a,t+1,b|1<<i))return 1;
  43.             }
  44.             J[v]=-1;
  45.             return 0;
  46.         }else if(u==v){
  47.             F(10)if(!(b&1<<i)){
  48.                 J[u]=i;
  49.                 if(rp(I,S+i*i,t+1,b|1<<i))return 1;
  50.             }
  51.             J[u]=-1;
  52.             return 0;
  53.         }else {
  54.             F(10)if(!(b&1<<i)){
  55.                 J[u]=i;
  56.                 if(~c){
  57.                     if(rp(I,S+i*c,t+1,b|1<<i))return 1;
  58.                 }else{
  59.                     FF(10)if(i^j&&!(b&1<<j)){
  60.                         J[v]=j;
  61.                         if(rp(I,S+i*j,t+1,b|1<<j|1<<i))return 1;
  62.                     }
  63.                     J[v]=-1;
  64.                 }
  65.             }
  66.             J[u]=-1;
  67.             return 0;
  68.         }
  69.         return 0;
  70.     }
  71.     int u=m[I],c=gt(u);
  72.     if(~c)return c==S%10&&mm(I+1,S/10,b);
  73.     if(b&1<<(S%10))return 0;
  74.     J[u]=S%10;
  75.     if(mm(I+1,S/10,b|1<<(S%10)))return 1;
  76.     J[u]=-1;
  77.     return 0;
  78. }
  79. bool mm(int I,int x,int b){
  80.     if(!J[X]||!J[Y]||!J[Z])return 0;//NEW
  81.     if(I==C)return !x;
  82.     return rp(I,x,0,b);
  83. }
  84. void mp(){
  85.     CL(J,-1),reverse(s,s+A),reverse(r,r+B),reverse(m,m+C);
  86.     assert(mm(0,0,0));
  87.     reverse(s,s+A),reverse(r,r+B),reverse(m,m+C);
  88.     assert(rd(s,A)*rd(r,B)==rd(m,C));//TODO ASS
  89.     tf(s,A),tf(r,B),tf(m,C);
  90.     printf("%s * %s = %s\n",s,r,m);
  91. }
  92. //ADDITION
  93. bool ad(int I,bool x,int b);
  94. bool rec(int I,int S,int t,int b){
  95.     int u=t?t>1?m[I]:r[I]:s[I],a;
  96.     if(t<2){
  97.         a=gt(u);
  98.         if(~a)return rec(I,S+a,t+1,b);
  99.         F(10)if(!(b&1<<i)){
  100.             J[u]=i;
  101.             if(rec(I,S+i,t+1,b|1<<i))return 1;
  102.         }
  103.         J[u]=-1;
  104.         return 0;
  105.     }
  106.     int c=gt(u);
  107.     if(~c)return c==S%10&&ad(I+1,S/10,b);
  108.     if(b&1<<(S%10))return 0;
  109.     J[u]=S%10;
  110.     if(ad(I+1,S/10,b|1<<(S%10)))return 1;
  111.     J[u]=-1;
  112.     return 0;
  113. }
  114. bool ad(int I,bool x,int b){
  115.     if(!J[X]||!J[Y]||!J[Z])return 0;//NEW
  116.     if(I==C)return !x;
  117.     return rec(I,x,0,b);
  118. }
  119. void add(){
  120.     CL(J,-1),reverse(s,s+A),reverse(r,r+B),reverse(m,m+C);
  121.     assert(ad(0,0,0));
  122.     reverse(s,s+A),reverse(r,r+B),reverse(m,m+C);
  123.     assert(rd(s,A)+rd(r,B)==rd(m,C));//TODO ASS
  124.     tf(s,A),tf(r,B),tf(m,C);
  125.     printf("%s + %s = %s\n",s,r,m);
  126. }
  127. int main(void){
  128.     while(~scanf("%s %c%s%*s%s",s,&c,r,m)){
  129.         A=strlen(s),B=strlen(r),C=strlen(m);
  130.         assert(C>=A&&B<=C);//TODO ASS - not true
  131.         X=*s,Y=*r,Z=*m;
  132.         if(A==1)X=32;
  133.         if(B==1)Y=32;
  134.         if(C==1)Z=32;
  135.         if(c==42)mp();
  136.         else add();
  137.         CL(s,0),CL(r,0),CL(m,0);
  138.     }
  139.     return 0;
  140. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement