#include #include #include #include #include #include using namespace std; constexpr int N = 10, T = 52; #ifndef ONLINE_JUDGE array D; array, T> Z; #endif void read_initial_input() { { int t; cin >> t; assert(t == T); } { int n; cin >> n; assert(n == N); } { int m; cin >> m; assert(m = 2'000'000); } #ifndef ONLINE_JUDGE for (int i = 0; i < N; ++i) cin >> D[i]; for (int t = 0; t < T; ++t) for (int i = 0; i < N; ++i) cin >> Z[t][i]; #endif } struct Data { int money; array s, p, r; }; #ifdef ONLINE_JUDGE void add_inv(const array &L) { cout << "1"; for (int l : L) cout << " " << l; cout << endl; } void do_ad(int x) { assert(1 <= x && x <= 5); cout << "2 " << x << endl; } Data get_next_data() { int m; cin >> m; array s, p, r; for (int i = 0; i < N; ++i) cin >> s[i]; for (int i = 0; i < N; ++i) cin >> p[i]; for (int i = 0; i < N; ++i) cin >> r[i]; return {m, s, p, r}; } #else int cur_money = 2'000'000; int turn_ = 0; array P_, R_; void add_inv(const array &L) { for (int i = 0; i < N; ++i) R_[i] += L[i], cur_money -= 500 * L[i]; assert(cur_money >= 0); } void do_ad(int x) { assert(1 <= x && x <= 5); cur_money -= 500'000 << (x - 1); assert(cur_money >= 0); for (int i = 0; i < N; ++i) P_[i] = min(60, P_[i] + x); } Data get_next_data() { array s{}; for (int i = 0; i < N; ++i) { if (R_[i] > 0) { s[i] = min(R_[i], int(floor(sqrt(R_[i]) * pow(1.05, P_[i]) * D[i] * Z[turn_][i]))); if (s[i] >= 0.3 * R_[i] && P_[i] < 60) P_[i] += 1; else if (s[i] < 0.1 * R_[i] && P_[i] > -60) P_[i] -= 1; R_[i] -= s[i]; cur_money += 1000 * s[i]; } } ++turn_; return {cur_money, s, P_, R_}; } #endif array Dlb = [] { array d; d.fill(0.5); return d; }(); array, T> S, P, R; double prob(int s, int p, int r, double d) { const double lb = clamp(double(s) / (sqrt(r) * pow(1.05, p) * (d + 0.1)), 0.75, 1.25); const double ub = r == s ? 1.25 : clamp(double(s + 1) / (sqrt(r) * pow(1.05, p) * d), 0.75, 1.25); return 2 * (ub - lb); } void update_Dlb(int cur_turn) { for (int i = 0; i < N; ++i) { array probs; probs.fill(1.0); for (int j = 0; j < 11; ++j) { const double d = 0.5 + 1.0 * j / 10; double tmp = 1.0; for (int t = 1; t <= cur_turn; ++t) { if (R[t][i] > 0) tmp *= prob(S[t][i], P[t - 1][i], R[t][i] + S[t][i], d); } probs[j] = tmp; } { double sum = accumulate(probs.begin(), probs.end(), 0.0); if (sum > 0) for (double &p : probs) p /= sum; } for (int j = 10; j > 0; --j) probs[j - 1] += probs[j]; // for (double p : probs) cerr << p << ' '; // cerr << endl; int j = 0; while (j + 1 < 11 && probs[j + 1] > 0.99) ++j; Dlb[i] = 0.5 + 1.0 * j / 10; } for (double p : Dlb) cerr << p << ' '; cerr << endl; } array calc_L(int money, const array &p, const array &r, int turn) { array L; for (int i = 0; i < N; ++i) { int lb = 1; auto check1 = [&] (int d) { return sqrt(r[i] + d) * pow(1.05, p[i]) * Dlb[i] * 0.75 >= 0.1 * (r[i] + d); }; // auto check3 = [&] (int d) { // return sqrt(r[i] + d) * pow(1.05, p[i]) * Dlb[i] * 0.75 >= 0.3 * (r[i] + d); // }; // while (lb < 1000 && !check3(lb)) ++lb; // if (lb < 1000) { // cerr << "A\n"; // int ub = lb + 1; // while (check3(ub) && ub < 1'000'000) ub *= 2; // if (turn > 50) cerr << lb << ' ' << ub << endl; // while (ub - lb > 1) { // const int m = (ub + lb) / 2; // if (check3(m)) lb = m; // else ub = m; // } // L[i] = lb; // } else { // cerr << "B\n"; // lb = 0; while (!check1(lb) && lb < 100) ++lb; if (lb == 100) continue; int ub = lb + 1; while (check1(ub) && ub < 1'000'000) ub *= 2; if (turn > 50) cerr << i << ' ' << lb << ' ' << ub << endl; while (ub - lb > 1) { const int m = (ub + lb) / 2; if (check1(m)) lb = m; else ub = m; } L[i] = lb; // } } int cost = 500 * reduce(L.begin(), L.end(), 0); while (money < cost) { array idx; iota(idx.begin(), idx.end(), 0); // sort(idx.begin(), idx.end(), [&p](int l, int r) { return p[l] < p[r]; }); for (int i : idx) { if (L[i] > 0) --L[i], cost -= 500; if (cost <= money) break; } } return L; } int main() { read_initial_input(); int money = 2'000'000; int score = 0; for (int t = 0; t < T; ++t) { if (t == 0) { array L; L.fill(9); add_inv(L); } else if (t < 40 && money > 500'000) { for (int x = 5; x > 0; --x) if (500'000 << (x - 1) < money) { do_ad(x); break; } } else { array L = t > 0 ? calc_L(money, P[t - 1], R[t - 1], t) : calc_L(money, {}, {}, t); add_inv(L); } const auto [m, s, p, r] = get_next_data(); // update_Dlb(t); money = m; score += reduce(s.begin(), s.end(), 0); S[t] = s; P[t] = p; R[t] = r; cerr << m << ' ' << reduce(s.begin(), s.end(), 0) << endl; for (int i = 0; i < N; ++i) cerr << s[i] << ' ' << p[i] << ' ' << r[i] << endl; cerr << endl; } cerr << "score = " << score << endl; }