Chinaunix首页 | 论坛 | 博客
  • 博客访问: 342917
  • 博文数量: 122
  • 博客积分: 5000
  • 博客等级: 大校
  • 技术积分: 1191
  • 用 户 组: 普通用户
  • 注册时间: 2009-10-24 11:12
文章分类

全部博文(122)

文章存档

2010年(122)

我的朋友

分类: C/C++

2010-04-22 15:13:53

一、问题描述

Description

A kind of virus has attacked the X planet, and many lives are infected. After weeks of study, The CHO (Creature Healthy Organization) of X planet finally finds out that this kind of virus has two kind of very simple DNA, and can be represented by 101 and 111. Unfortunately, the lives on the planet also have DNA formed by 0s and 1s. If a creature's DNA contains the virus' DNA, it will be affected; otherwise it will not. Given an integer L, it is clear that there will be 2 ^ L different lives, of which the length of DNA is L. Your job is to find out in the 2 ^ L lives how many won't be affected?

Input

The input contains several test cases. For each test case it contains a positive integer L (1 <= L <= 10 ^ 8). The end of input is indicated by end-of-file.

Output

For each test case, output K mod 2005, here K is the number of lives that will not be affected.

Sample Input

4

Sample Output

9

二、解题思路

可以推出递推公式f(n)=f(n-1)+f(n-3)+f(n-4)。然后输出1000结果查看结果的循环规律,得到200

三、代码

 

#include<iostream>
using namespace std;
int ans[205];
void Calculate()
{

    ans[0]=1;
    ans[1]=2;
    ans[2]=4;
    ans[3]=6;
    ans[4]=9;
    ans[5]=15;
    for(int i=6;i<200;++i)
    {
        ans[i]=ans[i-1]+ans[i-3]+ans[i-4];
        ans[i]%=2005;
    }    
}
int getNum(int n)
{
    n%=200;
    return ans[n];
}
int main()
{
    int n;
    Calculate();
    while(scanf("%d",&n)!=EOF)
    {
        printf("%d\n",getNum(n));
    }
    return 0;
}


阅读(1033) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~