AOJ1056 Ben Toh

問題
初日、半額弁当は100％入手できる。2日目は50％の確率で入手できる。
3日目は、2日目で入手出来たのなら、25％の確率で入手できる。
2日目で入手できなかったなら、再び100％の確率で入手できるようになる。
以下このアルゴリズムをN日まで繰り返したとき、N日間で入手できる半額弁当の数の期待値を求めよ。

N <= 10^5
10^(-2)以下の誤差は許される。

解説

#include <bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)

// 連続j日半額弁当を得ることができているとき、i日目に得ることの出来る半額弁当の個数(期待値)
double dp[100011][22];

// i日までに得ることの出来た半額弁当の個数(期待値)
double dp2[100001];

int main() {
  dp[1][1] = 1;

  REP(i, 1, 100001) {
    rep(j, 20) {
      dp[i+1][j+1] = dp[i][j] * pow(0.5, j);
      dp[i+1][0] += dp[i][j] * (1.0 - pow(0.5, j));
    }
  }

  rep(i, 100001) {
    double sum = 0.0;
    REP(j, 1, 20) sum += dp[i+1][j]; // j=0は半額弁当得ることが出来なかったので外す
    dp2[i+1] = sum + dp2[i];
  }
  
  int n;
  while(cin >> n && n)
    printf("%.10f\n", dp2[n]);

  return 0;
}