首页 > ACM题库 > HDU-杭电 > HDU 2832-Snail’s trouble-分治-[解题报告]HOJ
2014
02-17

HDU 2832-Snail’s trouble-分治-[解题报告]HOJ

Snail’s trouble

问题描述 :

Once upon a time, there was a poor snail. Every day, it tried very hard to crawl forward, while there was a keeper who’d like to maltreat this poor little snail. The snail was crawling on a one-meter rubber band at first, and it can move on k cm every minute. But after that, the keeper stretches the rubber band quickly, and it would be elongated one meter, during that the distances ratio between the snail and the two endpoints remain unchanged. In the next minute, little snail tried to keep moving forward again.
“Can I finally get to the endpoint?”
The snail often asked himself such a question because he was afraid he would never succeed. Now, we hope you can tell this poor snail when he would reach the endpoint.

输入:

Every line of the input contains an integer number k, indicating that the snail moved forward k cm every minute. (5 <= k <= 100)

输出:

Every line of the input contains an integer number k, indicating that the snail moved forward k cm every minute. (5 <= k <= 100)

样例输入:

10
100

样例输出:

12367
1

/*
分析:
    简单的数学题。
    第一分钟爬(k/100)m,第二分钟(k/200)m、第三分钟
(k/300)m……所以思路就出来了。。

                                                   2013-03-06
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"math.h"
#define N 111
int ans[N];
void init()
{
	ans[5]=272400600;
	ans[6]=9717617;
	ans[7]=898515;
	int k,q;
	double t,temp;
	for(k=8;k<=100;k++)
	{
		t=0;
		temp=1;
		q=0;
		while(t<100)
		{
			t+=k/temp;
			temp++;
			q++;
		}
		ans[k]=q;
	}
}
int main()
{
	init();
	int k;
	while(scanf("%d",&k)!=-1)
		printf("%d\n",ans[k]);
	return 0;
}

解题参考:http://blog.csdn.net/ice_crazy/article/details/8643625