VIRUS OUTBREAK题解

链接：https://ac.nowcoder.com/acm/contest/7818/J
来源：牛客网

题目描述
The State Veterinary Services Department recently reported an outbreak of a newly found cow disease. All cows found to have affected by the disease have since euthanized because of the risk to the industry. Number of affected cows increased to 21, 34 and reached 55 after eight, nine and ten hours respectively.
You have been assigned by the authority to study the pattern of the outbreak and develop a program to predict the next number of affected cows so that the authorities could prepare and act accordingly.
输入描述:
Input will consist of a series of positive integer numbers no greater than 490 each on a separate line represent the hours. The input process will be terminated by a line containing -1.
输出描述:
For each input value, the output contains a line in the format:Hour X:Y cow(s) affected , where X is the hour, and Y is the total affected cows that need to be euthanized based on the hour given by X.
示例1
输入
1
4
6
11
-1
输出
Hour: 1: 1 cow(s) affected
Hour: 4: 3 cow(s) affected
Hour: 6: 8 cow(s) affected

#include<bits/stdc++.h>
using namespace std;
const int N = 1000;
int a[N][N], len[N];
int main()
{
    len[1]=1;//存第i个斐波拉契数列的长度
    len[2]=1;
    a[1][1]=1;
    a[2][1]=1;
    for(int i=3;i<=500;++i)
    {
        for(int j=1;j<=len[i-1];++j)//每一位上直接相加
            a[i][j]=a[i-1][j]+a[i-2][j];
        for(int j=1;j<=len[i-1];++j)//每一位进位
            a[i][j+1]+=a[i][j]/10,a[i][j]%=10;
        len[i]=len[i-1];
        if(a[i][len[i]+1])len[i]++;
    }
    int x;
    while(~scanf("%d",&x)&&(x+1))
    {
        printf("Hour: %d: ",x);
        for(int i=len[x];i;--i)
            printf("%d",a[x][i]);
        puts(" cow(s) affected");
    }
    return 0;
}