diff options
| -rw-r--r-- | 21.5/feb/gold/camp.cpp | 39 |
1 files changed, 39 insertions, 0 deletions
diff --git a/21.5/feb/gold/camp.cpp b/21.5/feb/gold/camp.cpp new file mode 100644 index 0000000..1425fdb --- /dev/null +++ b/21.5/feb/gold/camp.cpp @@ -0,0 +1,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; +} |