列表

详情

NC200121. Logs Stacking

描述

Daxinganling produces a lot of timber. Before loading onto trains, the timber jacks will place the logs to some place within no more than two logs' height first. Looking from the sideway, the figure of a logs stack is as follows:

We have known that the number of logs in each layer is fewer than the lower layer for at least one log, and that in each layer the logs are connected in a line.
In the figure above, there are 4 logs in the bottom layer of the stack, and 3 logs in the top layer of the stack. So the picture shows one kind of figures with 7 logs accumulated together.
Now, given the total number of logs, Little Gyro wants to know how many possible figures there may be.

输入描述

There are multiple test cases. The first line of the input contains an integer T (1 ≤ T ≤ ), indicating the number of test cases. For each test case:
Each line contains one integer n (1 ≤ n ≤ 2×), indicating the total number of logs.

输出描述

For each test case in the input, you should output the corresponding number of possible figures.
Because the number may be very large, just output the number mod 10000.

示例1

输入: 

5
1
3
5
7
2000000000

输出: 

1
2
5
13
3125

说明:

In the third sample, you can accumulate 5 logs within such following ways:
First, you can put all the 5 logs at the ground floor.
Then, you can put 4 logs at the bottom layer, and there are 3 positions for the last log to pile up.
After that, you can also put 3 logs at the bottom layer, while the other 2 logs at the top layer.
Above all, you can get 1 + 3 + 1 = 5 figures in order to accumulate 5 logs.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C(clang 3.9) 解法, 执行用时: 24ms, 内存消耗: 984K, 提交时间: 2019-12-07 22:10:26 

#include<stdio.h>
int main(){
    int ans[2000005];
    ans[1]=1;
    ans[2]=1;
    for(int i=3;i<100000;i++){
        ans[i]=(ans[i-1]+ans[i-2])%10000;
    }
    int t;
    scanf("%d",&t);
    while(t--){
        long long n;
        scanf("%lld",&n);
        n%=15000;
        printf("%d\n",ans[n]);
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 28ms, 内存消耗: 1264K, 提交时间: 2019-12-11 14:16:37 

#include<cstdio>
int num[15005];
int main(){
	int i,n,t;
	num[0]=0;num[1]=num[2]=1;
	for(i=3;i<=15000;i++){
		num[i]=(num[i-1]+num[i-2]+10000)%10000;
	}
	while(scanf("%d",&t)!=EOF){
		while(t--){
			scanf("%d",&n);
			printf("%d\n",num[n%15000]);
		}
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 20ms, 内存消耗: 864K, 提交时间: 2019-12-07 18:09:39 

#include<bits/stdc++.h>
using namespace std;
const int N=15000,mod=1e4;
int a[N+10]={0,1,1};
int t,n;
int main(){
	for(int i=3;i<N;i++){
		a[i]=(a[i-1]+a[i-2])%mod;
	}
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		printf("%d\n",a[n-(n-1)/N*N]);
	}
}

上一题

© 2024 nowcoder.com