PersonalCorpus 版 (精华区)

//1Y 

//3210 2003/09/01 12:53:28.046 Accepted 0:00.006 64 C++ 2722 - Light Bulbs 
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "ctype.h"
#include "string.h"
#include "memory.h"

#define LI4SIZE 200
#define EPS     1e-16
struct LI4{
    int a[LI4SIZE];
    int len;
    int sign; // 1 for positive, and 0 for negative
};


struct LF4{
    struct LI4 f;
    int sign,rank;// f/(10^rank)
};

/***********************************************************/

void LI4_set0L(struct LI4 *des);
void LI4_set1L(struct LI4 *des);
void LI4_copyLL(struct LI4 *des,struct LI4 *src);
void LI4_addLL(struct LI4 *des, struct LI4 *src);
void LI4_addL3(struct LI4 *des, struct LI4 *src1, struct LI4 *src2);
void LI4_mulLI(struct LI4 *des, int src);
void LI4_mulLLI(struct LI4 *des, struct LI4 *src1, int src2);
void LI4_shl4LI(struct LI4 *des, int src);
void LI4_shr4LI(struct LI4 *des, int src);
void LI4_mulLL(struct LI4 *des, struct LI4 *src);
void LI4_mulL3(struct LI4 *des, struct LI4 *src1, struct LI4 *src2);
void LI4_printfL(struct LI4 *des);
void LI4_sprintfSL(char *buf, struct LI4 *des);
void LI4_sscanfSL(char *buf, struct LI4 *des);
int LI4_strlenL(struct LI4 *des);
void LI4_divLII(struct LI4 *des, int src, int &mod);
int LI4_abscmpLL(const void *a, const void *b);
int LI4_cmpLL(const void *a, const void *b);
void LI4_abssubLL(struct LI4 *des, struct LI4 *src);
int LI4_is0L(struct LI4 *des);
int LI4_getrank4L(struct LI4 *des);

/***********************************************************/
int  LF4_is0F(struct LF4 *des);
void LF4_cuttail0F(struct LF4 *des);
void LF4_set0F(struct LF4 *des);
void LF4_set1F(struct LF4 *des);
void LF4_copyFF(struct LF4 *des, struct LF4 *src);
void LF4_addFF(struct LF4 *des, struct LF4 *src);
void LF4_addF3(struct LF4 *des, struct LF4 *src1, struct LF4 *src2);
void LF4_mulFd(struct LF4 *des, double src);
void LF4_mulFFd(struct LF4 *des, struct LF4 *src1, double src2);
void LF4_shlFi(struct LF4 *des, int src);
void LF4_shrFi(struct LF4 *des, int src);
void LF4_mulFF(struct LF4 *des, struct LF4 *src);
void LF4_mulF3(struct LF4 *des, struct LF4 *src1, struct LF4 *src2);
void LF4_sprintfSF(char *buf, struct LF4 *des);

/***********************************************************/

int  LF4_is0F(struct LF4 *des)
{
    return LI4_is0L(&(des->f));
}

/***********************************************************/

void LF4_cuttail0F(struct LF4 *des)
{
    int i;
    
    i = LI4_getrank4L(&(des->f));
    des->rank -= 4 * i;
    LI4_shr4LI(&(des->f),i);
}

/***********************************************************/

void LF4_set0F(struct LF4 *des)
{
    LI4_set0L(&(des->f));
    des->sign=1;
    des->rank=0;
}
/***********************************************************/
void LF4_set1F(struct LF4 *des)
{
    LI4_set1L(&(des->f));
    des->sign=1;
    des->rank=0;
}
/***********************************************************/
void LF4_copyFF(struct LF4 *des, struct LF4 *src)
{
    LI4_copyLL(&(des->f), &(src->f));
    des->sign = src->sign;
    des->rank = src->rank;
}   
/***********************************************************/
void LF4_addFF(struct LF4 *des, struct LF4 *src)
{
    int k;
    if (des->rank > src->rank) {
        k=des->rank - src->rank;
        LI4_shl4LI(&(des->f),k/4);
        switch(k%4) {
            case 1: LI4_mulLI(&(des->f),10);    break;
            case 2: LI4_mulLI(&(des->f),100);   break;
            case 3: LI4_mulLI(&(des->f),1000);  break;
        }
        des->rank = src->rank;
    } else if (des->rank < src->rank) {
        k=src->rank - des->rank;
        LI4_shl4LI(&(src->f),k/4);
        switch(k%4) {
            case 1: LI4_mulLI(&(src->f),10);    break;
            case 2: LI4_mulLI(&(src->f),100);   break;
            case 3: LI4_mulLI(&(src->f),1000);  break;
        }
        src->rank = des->rank;
    }
    
    des->f.sign = des->sign;
    src->f.sign = src->sign;
    LI4_addLL(&(des->f),&(src->f));
    des->sign = des->f.sign;
    des->f.sign = 1;
    src->f.sign = 1;
    LF4_cuttail0F(des);
}
        
/***********************************************************/

void LF4_addF3(struct LF4 *des, struct LF4 *src1, struct LF4 *src2)
{
    LF4_copyFF(des,src1);
    LF4_addFF(des,src2);
}

/***********************************************************/

void LF4_mulFd(struct LF4 *des, double src)
{
    char s[24];
    int k;
    struct LI4 temp;
    double d;
    
    if (LI4_is0L(&(des->f))||(src==0)) {
        LF4_set0F(des);
        return;
    }
    
    if (src<0) {
        src = -src;
        des->sign = 1 - des->sign;
    }
    for (k=0,d=1;src*d-floor(src*d)>EPS;k++,d*=10);
    sprintf(s,"%.0lf",src*d);
    LI4_sscanfSL(s,&temp);
    LI4_mulLL(&(des->f),&temp);
    des->rank += k;
    LF4_cuttail0F(des);
}   

/***********************************************************/

void LF4_mulFFd(struct LF4 *des, struct LF4 *src1, double src2)
{
    LF4_copyFF(des,src1);
    LF4_mulFd(des, src2);
}

/***********************************************************/

void LF4_shlFi(struct LF4 *des, int src)
{
    if (LF4_is0F(des)||(src<=0)) return;
    des->rank -= src;
}

/***********************************************************/

void LF4_shrFi(struct LF4 *des, int src)
{
    if (LF4_is0F(des)||(src<=0)) return;
    des->rank += src;
}

/***********************************************************/

void LF4_mulFF(struct LF4 *des, struct LF4 *src)
{
    if (LF4_is0F(des)||LF4_is0F(src)) {
        LF4_set0F(des);
        return;
    }
    if (des->sign == src->sign) des->sign = 1; else des->sign = 0;
    LI4_mulLL(&(des->f),&(src->f));
    des->rank += src->rank;
    LF4_cuttail0F(des);
}   

/***********************************************************/

void LF4_mulF3(struct LF4 *des, struct LF4 *src1, struct LF4 *src2)
{
    LF4_copyFF(des,src1);
    LF4_mulFF(des, src2);
}

/***********************************************************/

void LF4_printfF(struct LF4 *des)
{
    
}

/***********************************************************/

void LF4_sprintfSF(char *buf, struct LF4 *des)
{
    int i,j,k;
    
    LI4_sprintfSL(buf,&(des->f));
    k=strlen(buf);
    if(des->rank<0) {
        for (i=0,j=k;i>des->rank;i--,j++) buf[j]='0';
        buf[j]=0;
        k-=des->rank;
    } else if(des->rank>0) {
        if (des->rank>=k) {
            j=des->rank-k+2;
            for (i=k;i>=0;i--) buf[i+j]=buf[i];
            for (i=2;i<j;i++) buf[i]='0';
            buf[0]='0'; buf[1]='.';
            k+=j;
        } else {
            j=k-des->rank;
            for (i=k;i>=j;i--) buf[i+1]=buf[i];
            buf[j]='.';
            ++k;
        }
    } else {
        buf[k++]='.';
        buf[k]=0;
    }
    for (i=k-1;i>0;i--) if ((buf[i]!='0')||(buf[i]=='.')) break;
    
    //if (buf[i]=='.') buf[i]=0; else buf[i+1]=0;
    buf[i+1]=0;
}   
    
            
    
            
        
            
            
            
        
    
    
/***********************************************************/
/***********************************************************/
/***********************************************************/

void LI4_set0L(struct LI4 *des)
{
    memset(des,0,sizeof(struct LI4));
    des->sign=1;
    des->len=1;
}

/***********************************************************/

void LI4_set1L(struct LI4 *des)
{
    LI4_set0L(des);
    des->a[0]=1;
}

/***********************************************************/

void LI4_copyLL(struct LI4 *des,struct LI4 *src)
{
    memcpy(des->a, src->a, src->len*4);
    des->len=src->len;
    des->sign=src->sign;
}

/***********************************************************/

void LI4_addLL(struct LI4 *des, struct LI4 *src)
{
    int i,j,k;
    struct LI4 temp;

    if (des->sign==src->sign) {
        k=0; i=0;
        while ((i<des->len)||((i<src->len))) {
            des->a[i]+=src->a[i];
            des->a[i]+=k;
            k=des->a[i]/10000;
            des->a[i]%=10000;
            i++;
        }
        if (k!=0) { des->a[i]=k; i++; }
        des->len=i;
    } else {
        k=LI4_abscmpLL(des,src);
        if (k==0) {
            LI4_set0L(des);
            return;
        } else if (k>0) {
            LI4_abssubLL(des,src);
        } else {
            k=des->sign;
            LI4_copyLL(&temp,src);
            LI4_abssubLL(&temp,des);
            LI4_copyLL(des,&temp);
            des->sign=1-k;
        }
    }
}

/***********************************************************/

void LI4_addL3(struct LI4 *des, struct LI4 *src1, struct LI4 *src2)
{
    LI4_copyLL(des,src1);
    LI4_addLL(des,src2);
}

/***********************************************************/

void LI4_mulLI(struct LI4 *des, int src)
{
    int i,j,k;

    k=0; i=0;
    while ((i<des->len)||(k>0)) {
        des->a[i]*=src;
        des->a[i]+=k;
        k=des->a[i]/10000;
        des->a[i]%=10000;
        i++;
    }
    des->len=i;
}

/***********************************************************/

void LI4_mulLLI(struct LI4 *des, struct LI4 *src1, int src2)
{
    LI4_copyLL(des,src1);
    LI4_mulLI(des,src2);
}

/***********************************************************/

void LI4_shl4LI(struct LI4 *des, int src)
{
    int i;
    
    if (src<=0) return;
    for (i=des->len-1;i>=0;i--)
        des->a[i+src]=des->a[i];
    for (i=0;i<src;i++) des->a[i]=0;
    des->len+=src;
}

/***********************************************************/

void LI4_shr4LI(struct LI4 *des, int src)
{
    int i;
    
    if (src>=des->len) {
        LI4_set0L(des);
        return;
    }
    if (src<=0) return;
    for (i=src;i<des->len;i++) 
        des->a[i-src]=des->a[i];
    for (i=des->len-src;i<des->len;i++) des->a[i]=0;
    des->len-=src;
}

/***********************************************************/

void LI4_mulLL(struct LI4 *des, struct LI4 *src)
{
    int i,j,k;
    struct LI4 temp1,temp2;

    LI4_set0L(&temp2);
    for (i=0;i<src->len;i++) {
        LI4_set0L(&temp1);
        LI4_mulLLI(&temp1,des,src->a[i]);
        LI4_shl4LI(&temp1,i);
        LI4_addLL(&temp2,&temp1);
    }
    LI4_copyLL(des,&temp2);
}

/***********************************************************/

void LI4_mulL3(struct LI4 *des, struct LI4 *src1, struct LI4 *src2)
{
    LI4_copyLL(des,src1);
    LI4_mulLL(des,src2);
}

/***********************************************************/

void LI4_printfL(struct LI4 *des)
{
    int i;

    if (des->len<=0) return;
    if (LI4_is0L(des)) { printf("0"); return; }

    if (des->sign==0) printf("-");
    i=des->len-1;
    printf("%d",des->a[i]);
    while (i>0) {
        i--;
        if (des->a[i]<1000) printf("0");
        if (des->a[i]<100) printf("0");
        if (des->a[i]<10) printf("0");
        printf("%d",des->a[i]);
    }
}

/***********************************************************/

void LI4_sprintfSL(char *buf, struct LI4 *des)
{
    int i,j,k;
    if (des->len<=0) return;
    buf[0]=0;

    for (i=des->len-1;i>=0;i--)  if (des->a[i]>0) {
        sprintf(buf+strlen(buf),"%d",des->a[i]);
        break;
    }
    if (i<0) {
        sprintf(buf+strlen(buf),"0");
        return;
    }
    for (j=i-1;j>=0;j--) {
        if (des->a[j]<1000) sprintf(buf+strlen(buf),"0");
        if (des->a[j]<100) sprintf(buf+strlen(buf),"0");
        if (des->a[j]<10) sprintf(buf+strlen(buf),"0");
        sprintf(buf+strlen(buf),"%d",des->a[j]);
    }
}

/***********************************************************/

void LI4_sscanfSL(char *buf, struct LI4 *des)
{
    int i,j,k,p[4]={1,10,100,1000};
    j=0;k=0;
    LI4_set0L(des);

    for (i=strlen(buf)-1;(i>=0)&&(isdigit(buf[i]));i--) {
        des->a[k]+=(buf[i]-48)*p[j];
        if (j==3) { j=0; k++;} else j++;
    }
    if (i>=0)
        if (buf[i]=='-') des->sign=0; else des->sign=1;
    while ((des->a[k]==0)&&(k>0)) k--;
    des->len=k+1;
}

/***********************************************************/

int LI4_strlenL(struct LI4 *des)
{
    char buf[100000];
    LI4_sprintfSL(buf,des);
    return strlen(buf);
}

/***********************************************************/

void LI4_divLII(struct LI4 *des, int src, int &mod)
{
    int i,k,j;
    if (des->len==0) {
        mod = 0;
        return;
    }
    k=0;
    for (i=des->len-1;i>=0;i--) {
        des->a[i]+=k*10000;
        k=des->a[i]%src;
        des->a[i]/=src;
    }
    mod=k;
    for (i=des->len-1; i>0;i--)
        if (des->a[i]!=0) break;
    des->len = i+1;
}

/***********************************************************/

int LI4_abscmpLL(const void *a, const void *b)
{
    struct LI4 *x=(struct LI4 *)a;
    struct LI4 *y=(struct LI4 *)b;

    if (x->len>y->len) return 1;
    if (x->len<y->len) return -1;
    if (x->a[x->len-1]>y->a[y->len-1]) return 1;
    if (x->a[x->len-1]<y->a[y->len-1]) return -1;
    return 0;
}

/***********************************************************/

int LI4_cmpLL(const void *a, const void *b)
{
    struct LI4 *x=(struct LI4 *)a;
    struct LI4 *y=(struct LI4 *)b;

    if (x->sign > y->sign) return 1;
    if (x->sign < y->sign) return -1;
    if (x->sign == 1) return LI4_abscmpLL(a,b); else return - LI4_abscmpLL(a,b);
}

/***********************************************************/

void LI4_abssubLL(struct LI4 *des, struct LI4 *src)
{
    int i,j,k;

    k=0;
    for (i=0;i<des->len;i++) {
        if ((des->a[i]-=src->a[i]+k)<0) {
            des->a[i]+=10000;
            k=1;
        } else k=0;
    }
    for (i=des->len-1;(i>=0)&&(des->a[i]==0);i--) ;
    if (i<0) des->len=1; else des->len=i+1;
}

/***********************************************************/

int LI4_is0L(struct LI4 *des)
{
    if ((des->len==1)&&(des->a[0]==0)) return 1; else return 0;
}

/***********************************************************/

int LI4_getrank4L(struct LI4 *des)
{
    int i;
    
    if (LI4_is0L(des)) return 0;
    for (i=0;i<des->len;i++) if (des->a[i]) break;
    return i;
}



void main()
{

#ifndef ONLINE_JUDGE
    freopen ("i","r",stdin);freopen ("o","w",stdout);
#endif

    struct LI4 q,one;
    char s[400],*t,a[400],b[400];
    int dp[400][2][2],i,j,k,la,lb,tot=0;    
    while (gets(s)) {
        la=lb=0;
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        t=strtok(s," ");
        LI4_sscanfSL(t,&q);
        while (!LI4_is0L(&q)) {
            LI4_divLII(&q,2,k); a[la++]=k;
        }
        t=strtok(NULL," ");
        LI4_sscanfSL(t,&q);
        while (!LI4_is0L(&q)) {
            LI4_divLII(&q,2,k); b[lb++]=k;
        }
        if ((la==0)&&(lb==0)) break;
        if (la<lb) la=lb;
        for (i=0;i<la;i++) a[i]^=b[i];

        memset(dp,50,sizeof(dp));
        dp[0][1][1]=1;
        dp[0][0][0]=0;

        for (i=1;i<la;i++) {
            dp[i][0][0]=dp[i-1][0][a[i-1]];
            dp[i][0][1]=dp[i-1][1][a[i-1]];
            dp[i][1][0]=dp[i-1][1][1-a[i-1]]+1;
            dp[i][1][1]=dp[i-1][0][1-a[i-1]]+1;
        }
        if (tot) printf("\n");
        printf("Case Number %d: ",++tot);
        if ((dp[la-1][0][a[la-1]]>400)&&(dp[la-1][1][a[la-1]]>400)) {
            printf("impossible\n"); 
            continue;
        }
        
        if (dp[la-1][0][a[la-1]]>dp[la-1][1][a[la-1]]) j=1; else j=0;
        k=a[la-1];
        LI4_set0L(&q);
        LI4_set1L(&one);
        for (i=la-1;i>0;i--) {
            LI4_mulLI(&q,2);
            if (j==1) { LI4_addLL(&q,&one); j=1-k; k=1-a[i-1]; } else { j=k; k=a[i-1]; }
        }
        LI4_mulLI(&q,2); if (j==1) LI4_addLL(&q,&one); 
        LI4_printfL(&q);
        printf("\n");
    }
}