当前位置: 代码迷 >> 综合 >> 二分奇葩 HDU Problem H
  详细解决方案

二分奇葩 HDU Problem H

热度:78   发布时间:2024-01-15 08:37:33.0

Problem H

Time Limit : 3000/1000ms (Java/Other)   Memory Limit :32768/32768K (Java/Other)

Total Submission(s) : 1   Accepted Submission(s) : 1

Problem Description

A有1数m,B来猜.B每猜一次,A就说&quot;太大&quot;,&quot;太小&quot;或&quot;对了&quot; 。 <br>问B猜n次可以猜到的最大数。 <br>

 

 

Input

第1行是整数T,表示有T组数据,下面有T行 <br>每行一个整数n (1 ≤ n ≤ 30) <br>

 

 

Output

猜n次可以猜到的最大数<br>

 

 

Sample Input

2

1

3

 

 

Sample Output

1

7

算法分析:

题意能理解: 
最多猜n次一定可以猜到1至m(闭区间)内的任意数字,求m的最大值。

要猜到的最大的数字m,即在1到m间的每一个数,你都能在n次内把它猜出来。所以说在最坏的情况下,在1到m间,你最多只要猜log2(m+1)(取整)次,所以易知m=2^n - 1,即猜n次,你能猜到的最大的数为2^n - 1。

二分实现:假设要查找的最大数是m, 则,

第一次查找,(m+1)/2=m;得m=1; 

第二次查找,((m+1)/2+1+m)/2=m;得m=3; 

第三次查找,(((m+1)/2+1+m)/2+1+m)=m;得m=7; 

归纳:m=2^n-1;  

 

代码实现:

 

#include<bits/stdc++.h>
using namespace std;
int main()
{int T;cin>>T;while(T--){int n;cin>>n;int maxx=pow(2,n)-1;cout<<maxx<<endl;}return 0;
}

  相关解决方案