首页 > 代码库 > HDU2178 猜数字【水题】【推理】

HDU2178 猜数字【水题】【推理】

2024-11-22 20:32:39   202人阅读

猜数字

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3666    Accepted Submission(s): 2620

Problem Description
A有1数m，B来猜.B每猜一次，A就说"太大"，"太小"或"对了" 。 
问B猜n次可以猜到的最大数。 
 
Input
第1行是整数T,表示有T组数据，下面有T行 
每行一个整数n (1 ≤ n ≤ 30) 
 
Output
猜n次可以猜到的最大数
 
Sample Input
2
1
3
 
Sample Output
1
7
 
Author
Zhousc
 
Source

ECJTU 2008 Summer Contest


题目大意：有1~M的数字，最多猜N次一定能猜到1~M的任意数字，求M能达到的最大值。

思路：用二分法在最多N次的时候找到任意1~M的任意数字，N是已知的，二分的范围是1~M，

左边界为1，右边界为M，若想M最大，则尽量使取值向右边界靠。考虑N = 3，N = 4的情况。

N = 3时，每次取值都在区间右边取值，第一次二分后区间[(1+M)/2，M]，第二次二分后区间

[((1+M)/2+1+M)/2，M]，第三次二分后区间[(((1+M)/2+1+M)/2+1+M)/2，M]，此时，左

右区间等值，即(((1+M)/2+1+M)/2+1+M)/2 == M，用归纳法，可得M = 2^N-1。


#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
using namespace std;

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int N;
        cin >> N;
        double ans = pow(2,N) - 1;
        printf("%.0lf\n",ans);
    }

    return 0;
}


HDU2178 猜数字【水题】【推理】


联系
我们