Constraints

Time Limit: 1 secs, Memory Limit: 256 MB

Description

After realizing that there is much money to be made in software development, Farmer John has launched a small side business writing short programs for clients in the local farming industry. Farmer John's first programming task seems quite simple to him -- almost too simple: his client wants him to write a program that takes a number N as input, and prints 17 times N as output. Farmer John has just finished writing this simple program when the client calls him up in a panic and informs him that the input and output both must be expressed as binary numbers, and that these might be quite large. Please help Farmer John complete his programming task. Given an input number N, written in binary with at most 1000 digits, please write out the binary representation of 17 times N.

Input

* Line 1: The binary representation of N (at most 1000 digits).

Output

* Line 1: The binary representation of N times 17.

Sample Input

10110111

Sample Output

110000100111

Hint

The binary number 10110111 is equal to 183 in decimal form. 183 x 17 = 3111 is 110000100111 in binary format.

分析：

一开始正常的想法是将二进制转化为十进制，乘以17之后再换回2进制，但是发现由于二进制有1000位，转化为十进制没有能装下的类型，马上放弃这个想法。

然后分析二进制数，乘以17可以看成乘以（16+1），而乘以16则可以简单的在后面加上4个0完成。如二进制的1111乘以16结果是11110000,再加上1111可以得到结果11111111.

对于二进制的加法，我用了模拟手算加法，进位用temp记录，注意string里面的是字符类型char。

 1 #include<iostream>
 2 using namespace std;
 3 
 4 
 5 int main(){
 6     string n_binary;
 7     cin>>n_binary;
 8     string result_binary=n_binary+"0000";//乘以17可以先乘上16在加上本身
 9     n_binary="0000"+n_binary;//补足位数进行模拟手算
10     int len=result_binary.length();
11     int temp=0;//记录进位
12     for(int i=len-1;i>0;i--){//模拟手算加法
13         if((n_binary[i]-'0')+(result_binary[i]-'0')+temp<2){//不够进位
14             result_binary[i]=(n_binary[i]-'0')+(result_binary[i]-'0')+temp+'0';
15             temp=0;
16         }
17         else{
18             result_binary[i]=(n_binary[i]-'0')+(result_binary[i]-'0')+temp+'0'-2;
19             temp=1;
20         }
21     }
22     if(temp==1){//如果最高位有进位需要在前面补'1',而进位之后第二位变为'0'
23         result_binary[0]='0';
24         result_binary="1"+result_binary;
25     }
26     cout<<result_binary<<endl;
27     return 0;
28 }