https://projecteuler.net/problem=503
const int N = int(1e6) + 9;
int n = 1000000;
DB f[N];
// randomly choosing i elements from n elements,
// the expectation of the j-th element.
DB e(int i, int j){
return (DB)(n+1) / (i+1) * j;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("/users/xiaodao/desktop/Exercise/in.txt", "r", stdin);
//freopen("/users/xiaodao/desktop/Exercise/out.txt", "w", stdout);
#endif
f[n] = (n + 1.0) / 2;
int up = n - 1;
DWN(i, n, 1){
// in i-th round, we get j-th,
// we enumerate the cut-off point: k,
// that is, if j <= k, we stop.
f[i] = f[i + 1]; // if k=0
DB prob = 1, expe = 0;
// the prob we don't stop ..
// the expe if we stop.
REP_1_C(k, up){
expe += 1.0 / i * e(i, k); if (expe >= f[i]) break;
prob -= 1.0 / i;
if (expe + prob * f[i+1] < f[i]){
f[i] = expe + prob * f[i+1];
up = k;
}
}
}
printf("%.10f\n", f[1]);
}
// 3.8694550145
