1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;
using ii = pair<int, int>;
const int MX = 1e3+5;
double p[MX], e[MX];
inline double f(double y, double a, double b, double t) { return pow(a, t)*y + b*(1-pow(a, t))/(1-a); }
int main() {
cin.tie(0)->sync_with_stdio(0);
int T, K; cin >> T >> K; --T;
for (int i = 0; i <= T; ++i) {
double val = 1;
for (int j = 0; j < i; ++j) val = val/(i-j)*(T-j);
val = ldexp(val, -T);
if (i) p[i] = p[i-1], e[i] = e[i-1];
p[i] += val, e[i] += i*val;
}
double ans = T/2.0;
int i = 1, x = T/2;
while (i < K) {
int l = i+1, r = K;
// Repeatedly do a*ans+b
double a = p[x], b = T/2.0-e[x];
while (l < r) {
int m = (l+r)/2;
double y = ans;
if (f(y, a, b, m-i) > x+1) r = m;
else l = m+1;
}
ans = f(ans, a, b, l-i);
i = l, ++x;
}
cout << setprecision(14) << ans+1;
}
|
