poj 2116 Death to Binary? 模拟
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 1707 | Accepted: 529 |
Description
For example 1101001Fib = F0 + F3 + F5 + F6 = 1 + 5 + 13 + 21 = 40.
You may observe that every integer can be expressed in this base,
but not necessarily in a unique way - for example 40 can be also
expressed as 10001001Fib. However, for any integer there is a
unique representation that does not contain two adjacent digits 1 - we
call this representation canonical. For example 10001001Fib is a canonical Fibonacci representation of 40.
To prove that this representation of numbers is superior to the
others, ACM have decided to create a computer that will compute in
Fibonacci base. Your task is to create a program that takes two numbers
in Fibonacci base (not necessarily in the canonical representation) and
adds them together.
Input
input consists of several instances, each of them consisting of a single
line. Each line of the input contains two numbers X and Y in Fibonacci
base separated by a single space. Each of the numbers has at most 40
digits. The end of input is not marked in any special way.
Output
The first line contains the number X in the canonical
representation, possibly padded from left by spaces. The second line
starts with a plus sign followed by the number Y in the canonical
representation, possibly padded from left by spaces. The third line
starts by two spaces followed by a string of minus signs of the same
length as the result of the addition. The fourth line starts by two
spaces immediately followed by the canonical representation of X + Y.
Both X and Y are padded from left by spaces so that the least
significant digits of X, Y and X + Y are in the same column of the
output. The output for each instance is followed by an empty line.
Sample Input
11101 1101
1 1
Sample Output
100101
+ 10001
-------
1001000 1
+ 1
--
10
Source
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
#define ll long long
#define esp 1e-13
const int N=1e4+,M=1e6+,inf=1e9+,mod=;
string s1,s2,s3;
ll a[N];
void init()
{
a[]=;
a[]=;
for(int i=;i<=;i++)
a[i]=a[i-]+a[i-];
}
ll getnum(string aa)
{
int x=aa.size();
ll sum=;
for(int i=;i<x;i++)
if(aa[i]=='')
sum+=a[i];
return sum;
}
void check(ll x,string &str)
{
int i;
for(i=;i>=;i--)
if(x>=a[i])
break;
for(int t=i;t>=;t--)
if(x>=a[t])
{
str+='';
x-=a[t];
}
else
str+='';
if(i<)
str+='';
}
int main()
{
int x,y,i,z,t;
init();
while(cin>>s1>>s2)
{ reverse(s1.begin(),s1.end());
reverse(s2.begin(),s2.end());
ll num1=getnum(s1);
ll num2=getnum(s2);
ll num3=num1+num2;
s1.clear();
s2.clear();
s3.clear();
check(num1,s1);
check(num2,s2);
check(num3,s3);
printf(" ");for(i=;i<s3.size()-s1.size();i++)printf(" ");cout<<s1<<endl;
printf("+ ");for(i=;i<s3.size()-s2.size();i++)printf(" ");cout<<s2<<endl;
printf(" ");for(i=;i<s3.size();i++)printf("-");cout<<endl;
printf(" ");cout<<s3<<endl;
cout<<endl;
}
return ;
}
最新文章
- ajax获取数据的形象比喻,助于理解记忆
- SQL Server 日期和时间函数
- DS实验题 融合软泥怪-2 Heap实现
- Bower 自定义组件文件夹名称
- 北斗/GPS
- winform用户控件
- 某些输入文件使用或覆盖了已过时的 API
- 记录一次会话CRT
- Entity Framework Code First 常用方法集成
- java:I/O 往原文件追加内容
- eclipse安装ADT插件重启后不显示Android SDK Manager和Android Virtual Device Manager图标的一种解决办法
- 如何解决Python.h:No such file or directory
- ThinkPad E470笔记本电脑无声音、无线wifi功能(灰色)
- nginx负载均衡一:基础知识
- jquery 数组的操作
- [NOI 2015]寿司晚宴
- [转]Vue.js 入门教程
- Linux学习10-CentOS搭建nginx负载均衡环境
- Scrapy源码注解--CookiesMiddleware
- [Xarmrin.IOS]使用Build Host 在Windows上建置IOS程式及DeBug (转帖)