Head-to-Head Match

Head-to-Head Match

时间: 1ms        内存:64M

描述:

Our school is planning to hold a new exciting computer programming contest. During each round of the contest, the competitors will be paired, and compete head-to-head. The loser will be eliminated, and the winner will advance to next round. It proceeds until there is only one competitor left, who is the champion. In a certain round, if the number of the remaining competitors is not even, one of them will be chosed randomly to advance to next round automatically, and then the others will be paired and fight as usual. The contest committee want to know how many rounds is needed to produce to champion, then they could prepare enough problems for the contest.

输入:

The input consists of several test cases. Each case consists of a single line containing a integer N - the number of the competitors in total. 1 <= N <= 2,147,483,647. An input with 0(zero) signals the end of the input, which should not be processed.

输出:

For each test case, output the number of rounds needed in the contest, on a single line.

示例输入:

8
16
15
0

示例输出:

3
4
4

提示:

参考答案(内存最优[748]):

#include"stdio.h"
int main()
{
    long n,i;
    while(scanf("%ld",&n)&&n!=0)
    {
        for(i=0;n!=1; i++)
        {
            if(n%2==0)
            n/=2;
            else
            n=n/2+1;
        }
        printf("%ld\n",i);
    }
    return 0;
}

参考答案(时间最优[8]):

#include <stdio.h> 
#include <math.h> 
int main() 
{ 
    int n; 
    while(scanf("%d",&n)&&n) 
	{	
		if(n==1)printf("0\n");
		else printf("%d\n",(int)(log(n-1)/log(2))+1); 
	}
    return 0; 
} 

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注