2022 feb gold camp

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;
+}