174
HDU2178猜數字
HDU2178猜數字Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2716 Accepted Submission(s): 1955
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
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int n,m;
cin>>n;
while(n--)
{
cin>>m;
cout<<(int)pow(2,m)-1<<endl;
}
return 0;
}題意：最多猜n次一定可以猜到1至m(閉區間)內的任意數字，求m的最大值。公式不完全推導：
以n=3為例：
設閉區間為1到m，m即為所求.
由二分思想，盡量往右靠(每次取中間值加1為新的左邊界且右邊界不變)，
可列出等式，
(((((1+m)/2)+1+m)/2)+1+m)/2=m
解得，m=7.
推廣，當n=n時，歸納易得，
m=(2^n)-1.
最後更新：2017-04-03 12:54:38