// Update probabilty distribution step by step, taking O(n) per iteration. // Timed to stop after ~0.9 seconds, then uses the current distribution as an estimate. #include using namespace std; int main() { clock_t start = clock(); int n, i, k; cin >> n >> i >> k; vector h(n+1); for (int a = 1; a <= n; a++) { h[a] = h[a-1] + 1.0/a; } vector prob(n+1); prob[i] = 1; while (k--) { vector nprob(n+1); double s = 0; for (int b = 1; b <= n; b++) { s += prob[b]; nprob[b] = (b-1)*prob[b] + s*(h[n]-h[b-1]); } double t = 0; for (int b = n; b >= 1; b--) { nprob[b] = (nprob[b] + t)/n; t += prob[b]*(h[n]-h[b-1]); } swap(prob,nprob); if (double(clock()-start)/CLOCKS_PER_SEC > 0.9) break; } double E = 0; for (int a = 1; a <= n; a++) E += a*prob[a]; cout << fixed << setprecision(20) << E << endl; }