2015
02-22

# Guess Game

Bob plays the “guess the number right” with Alice recently,the game’s rule is that Alice give Bob a upper limit number N ,then he write any of a number on paper which Bob can’t know what it is and the number must be between 1 and N.Bob has many chances to guess the number and every time when Bob guesses Alice will tell him if his is bigger than the correct number or small than the correct number until he is right.
Now the Bob wanted to use binary search method to guess the right number, because he knows this method is quite fast to find the right number.

We test the problem in many cases.Each case begin with one integers N( 1<= N <= 100000 ).

We test the problem in many cases.Each case begin with one integers N( 1<= N <= 100000 ).

2
3

1.50
1.67

4.5749999先乘以100000–>457499.99再+0.5–>457500.49取整–>457500再除以100000–>4.57500保留2位小数输出–>4.58

#include<stdio.h>
#define eps 1e-6
double sum;
void expect(int now,int n,double s)
{
int d=n/2;
if(n==0) return;
sum+=s*now/n;
s=s*(1-1.0/n);
if(n%2)
expect(now+1,d,s);
else
{
expect(now+1,d,s*d/(n-1));
expect(now+1,d-1,s*(d-1)/(n-1));
}
}
int main()
{
int n,s;

while(~scanf("%d",&n))
{
sum=0.0;
expect(1,n,1.0);
printf("%.2lf\n",sum+eps);
}
return 0;
}

1. 因为是要把从字符串s的start位到当前位在hash中重置，修改提交后能accept，但是不修改居然也能accept

2. int L[m+1][n+1];这样定义出错，这个在gcc上可以编译通过 在VS上不行 应该改为new 或者vector

3. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮