はやし屋

競技プログラミングのメモ きたない

AOJ 1056: Ben Toh

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1056&lang=jp

つかいまわしたかった

#include<cstdio>
#include<algorithm>
using namespace std;
double dp[2][15];
double res[111111];
int main(){
  dp[0][0] = 1;
  
  double cur = 0;
  for(int i = 0 ; i < 111111 ; ++i){
    for(int j = 0 ; j < 14 ; ++j){
      double b = 1.0/(1<<j);
      cur += b * dp[i&1][j];
      dp[(i+1)&1][j+1] += dp[i&1][j]*b;
      dp[(i+1)&1][0] += dp[i&1][j]*(1.0-b);
      dp[i&1][j] = 0.0;
    }
    res[i] = cur;
  }
  for(int n;scanf("%d",&n)&&n;)printf("%lf\n",res[n-1]);
}