1 /*  2  POJ2166 Death to Binary?  3  http://poj.org/problem?id=2116  4  齐肯多夫定理  5   6  */  7 #include <cstdio>  8 #include <algorithm>  9 #include <cstring> 10 #include <cmath> 11 #include <vector> 12 #include <queue> 13 #include <iostream> 14 #include <map> 15 #include <set> 16 //#define test 17 using namespace std; 18 const int Nmax=1e6+7; 19 char s[50],a[50],b[50],c[50],tmp[50],t[50]; 20 long long f[50]; 21 vector<long long> v; 22 vector<long long>::iterator it; 23 long long scan() 24 { 25     char c=getchar();    26     while(c==‘ ‘||c==‘\n‘) 27         c=getchar(); 28     if(c==-1) 29         return -1; 30     int sz=0; 31     while(c>=‘0‘ && c<=‘1‘) 32     { 33         s[++sz]=c; 34         c=getchar(); 35     } 36     long long x=0LL; 37     for(int i=1;i<=sz;i++) 38     { 39         x+=1LL*(s[i]-‘0‘)*f[sz-i]; 40     } 41     return x; 42 } 43 int id(long long x) 44 { 45     int now=upper_bound(v.begin(),v.end(),x)-v.begin(); 46     if(now!=0) 47         now--; 48     return now; 49 } 50 char* get(long long x) 51 { 52    int sz=0; 53    for(int i=0;i<=40;i++) 54        tmp[i]=‘0‘; 55    //printf("\n"); 56    while(x>0) 57    { 58        //printf("x:%lld\n",x); 59        tmp[id(x)]=‘1‘; 60        sz=max(sz,id(x)); 61        //printf("%d ",id(x)); 62        //printf("%lld",f[id(x)]); 63        x-=f[id(x)]; 64    } 65    //printf("\n"); 66    //for(int i=0;i<=40;i++) 67        //printf("%c",tmp[i]); 68    //printf("\n"); 69     70    //printf("%s\n",tmp); 71   72    for(int i=sz;i>=0;i--) 73        t[sz-i]=tmp[i]; 74    t[sz+1]=‘\0‘; 75    return t; 76 } 77 void print() 78 { 79     int n=strlen(c); 80     int sum=n+2; 81     int an=strlen(a); 82     int bn=strlen(b); 83     for(int i=1;i<=sum-an;i++) 84         putchar(‘ ‘); 85     printf("%s\n",a); 86     putchar(‘+‘); 87     for(int i=1;i<=sum-bn-1;i++) 88         putchar(‘ ‘); 89     printf("%s\n",b); 90     putchar(‘ ‘); 91     putchar(‘ ‘); 92     for(int i=1;i<=n;i++) 93         putchar(‘-‘); 94     putchar(‘\n‘); 95     putchar(‘ ‘); 96     putchar(‘ ‘); 97     printf("%s\n\n",c); 98 } 99 int main()100 {101     #ifdef test102     #endif103     //freopen("poj2166.in","r",stdin);104     f[0]=1LL;105     f[1]=2LL;106     for(int i=2;i<41;i++)107         f[i]=f[i-1]+f[i-2];108     for(int i=0;i<=40;i++)109         v.push_back(f[i]);110     while(1)111     {112         long long x=scan();113         //printf("%lld\n",x);114         if(x==-1)115             break;116         long long y=scan();117         if(y==-1)118             break;119         long long ans=x+y;120         //long long ttt=40LL;121         //while(ttt>0)122         //{123             //printf("%d\n",id(ttt));124             //printf("%lld\n",f[id(ttt)]);125             //ttt-=f[id(ttt)];126         //}127         //strcpy(a,get(40LL));128         //printf("%s\n",a);129         strcpy(a,get(x));130         strcpy(b,get(y));131         strcpy(c,get(ans));132         print();133     }134     return 0;135 }