JS's Blog
0%

POJ 2116 Death to Binary_（模拟题）

Posted on Edited on In ,

题目链接：
http://acm.hust.edu.cn/vjudge/contest/70017#problem/T
题目大意：
读入两个01串，分别表示两个数X，Y
比如1101001表示 Fib = F0 + F3 + F5 + F6 = 1 + 5 + 13 + 21 = 40.
求这两个数的和，同样用01串表示结果 最后输出一个加法算式
如11101 1101
输出：
100101

  • 10001
    - - - - - - -
    1001000
    假设三个串长度分别为len1,len2,len3
    第一行：先输出len3+2-len1个空格，再输出第一个串
    第二行：先输出一个加号，再输出len3+1-len2个空格，再输出第二个串
    第三行：先输出两个空格，再输出len3个−-字符
    第四行：先输出两个空格，再输出第三个串

注意：
1.输入的串可能有前导零
2.可能有0 0 这样的极端数据
3.输入的两个串也需要处理，样例里没有给出，但是题意里有
比如输入111111应该输出10011001

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<map>
#include <algorithm>
#define mod 1000000007
using namespace std;
typedef long long ll;
ll n,ans,y;
ll Fb[100];
void init()
{
    Fb[0]=1;
    Fb[1]=2;
    for (int i = 2; i <= 44 ; i ++)
        Fb[i]=Fb[i-1]+Fb[i-2];
}

char s1[100],s2[100],s3[100];
int main()
{
    init();
    ll n1,n2;
    while (~scanf("%s%s",s1,s2))
    {
        n1=n2=0;
        int l1 = strlen(s1),l2=strlen(s2);
        for (int i = l1 -1  ; i >= 0 ; --i )
        {
            if (s1[i]=='1')
                n1 += Fb[l1-1-i];
        }
        for (int i = l2 -1  ; i >= 0 ; --i )
        {
            if (s2[i]=='1')
                n2 += Fb[l2-1-i];
        }
        ll ans = n1 + n2 ,tmp;
        {
            tmp = 0;
            int pos = lower_bound(Fb,Fb+45,n1)-Fb;
            if (Fb[pos]>n1) pos--;
            //printf("now pos = %d\n",pos);
            if (pos==-1)
            {
                s1[0]='0';
                pos= 0;
            }
            for (int i = pos ; i >=0 ; --i)
                if (tmp+Fb[i]<=n1)
                {
                    s1[pos-i]='1';
                    tmp += Fb[i];
                }
                else
                    s1[pos-i]='0';

            s1[pos+1]='\0';
            l1 = strlen(s1);
        }
        {
            tmp = 0;
            int pos = lower_bound(Fb,Fb+45,n2)-Fb;
            if (Fb[pos]>n2) pos--;
            //printf("now pos = %d\n",pos);
            if (pos==-1)
            {
                s2[0]='0';
                pos= 0;
            }
            for (int i = pos ; i >=0 ; --i)
                if (tmp+Fb[i]<=n2)
                {
                    s2[pos-i]='1';
                    tmp += Fb[i];
                }
                else
                    s2[pos-i]='0';

            s2[pos+1]='\0';
            l2 = strlen(s2);
        }
        tmp = 0;
        int pos = lower_bound(Fb,Fb+45,ans)-Fb;
        if (Fb[pos]>ans) pos--;
        //printf("now pos = %d\n",pos);
        if (pos==-1)
        {
            s3[0]='0';
            pos= 0;
        }
        for (int i = pos ; i >=0 ; --i)
            if (tmp+Fb[i]<=ans)
            {
                s3[pos-i]='1';
                tmp += Fb[i];
            }
            else
                s3[pos-i]='0';

        s3[pos+1]='\0';
        int l3 = strlen(s3);
        for (int i = 1 ; i <= l3+2 - l1 ; i ++)
	    putchar(' ');
        printf("%s\n",s1);
        putchar('+');
        for (int i = 1 ; i <=l3+1-l2;i++)
            putchar(' ');
        printf("%s\n",s2);
        printf("  ");
        for (int i = 1; i <= l3;i ++)
            putchar('-');
        putchar('\n');
        printf("  ");
        printf("%s\n\n",s3);
        }
    }
}