2016百度之星 资格赛 1002 Problem B 递推加大数
Problem B Accepts: 2515 Input 1leq N leq 2001≤N≤200 Output Sample Input 其实问题不难,就是一堆1要合并成,只有相邻的1才能合并. 2 111 1 2 1 1 #include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MOD=10000;
struct BigInt{
int data[110];
int len;
BigInt add(BigInt b){
BigInt ans;
ans.len = max(len,b.len);
memset(ans.data,0,sizeof(ans.data));
for(int i=0;i<ans.len;i++){
int num1 = 0,num2 = 0;
if(i<len)num1=data[i];
if(i<b.len)num2=b.data[i];
ans.data[i]+=num1+num2;
if(ans.data[i]>=MOD){
ans.data[i+1]+=ans.data[i]/MOD;
ans.data[i]%=MOD;
}
}
if(ans.data[ans.len]!=0)ans.len++;
return ans;
}
void out(){
printf("%d",data[len-1]);
for(int i=len-2;i>=0;i--)
printf("%04d",data[i]);
cout<<endl;
}
};
BigInt f[210];
int main(){
//freopen("tmp.in","r",stdin);
//freopen("hduB_1.out","w",stdout);
f[1].len=f[2].len=f[3].len=1;
f[1].data[0]=1;
f[2].data[0]=2;
f[3].data[0]=3;
for(int i=4;i<=200;i++)
f[i] = f[i-3].add(f[i-2].add(f[i-2]));
int n;
//for(int i=1;i<=200;i++)
// f[i].out();
while(cin>>n)
f[n].out();
return 0;
}
//
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |