HDU 5914 Triangle 数学找规律

Triangle

题目连接:

http://acm.hdu.edu.cn/showproblem.php?pid=5914

Description

Mr. Frog has n sticks, whose lengths are 1,2, 3⋯n respectively. Wallice is a bad man, so he does not want Mr. Frog to form a triangle with three of the sticks here. He decides to steal some sticks! Output the minimal number of sticks he should steal so that Mr. Frog cannot form a triangle with

any three of the remaining sticks.

Input

The first line contains only one integer T (T≤20), which indicates the number of test cases.

For each test case, there is only one line describing the given integer n (1≤n≤20).

Output

For each test case, output one line “Case #x: y”, where x is the case number (starting from 1), y is the minimal number of sticks Wallice should steal.

Sample Input

3

4

5

6

Sample Output

Case #1: 1

Case #2: 1

Case #3: 2

Hint

题意

你有1-n的n条边,让你拿走尽量少的边,使得剩下的边,任意取三个都不能组成三角形。

题解:

最后剩下的边是Fib数列就可以了,这样就保证了任意三个都不能组成三角形。

证明也很简单。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 25;
int dp[maxn];
int main()
{
dp[1]=1,dp[2]=1,dp[3]=1,dp[5]=1,dp[8]=1,dp[13]=1,dp[21]=1;
for(int i=1;i<=20;i++)
dp[i]+=dp[i-1];
for(int i=1;i<=20;i++)
dp[i]=i-dp[i];
int t;
scanf("%d",&t);
for(int cas=1;cas<=t;cas++){
int x;scanf("%d",&x);
printf("Case #%d: %d\n",cas,dp[x]);
}
}
上一篇:js实现环形菜单效果


下一篇:0014 Java学习笔记-集合-HashMap集合