#include using namespace std; using namespace chrono; using uint = unsigned int; using lint = long long int; using ulint = unsigned long long int; template using V = vector; template using VV = V< V >; template void assign(V& v, int n, const U& a) { v.assign(n, a); } template void assign(V& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); } lint ceilll(lint a, lint b) { assert(a >= 0 and b > 0); return (a + b - 1) / b; } // [a, b) int rng(int a, int b) { static mt19937 mt(steady_clock::now().time_since_epoch().count()); assert(a < b); return uniform_int_distribution<>(a, b - 1)(mt); } // input constexpr int T = 10'000; string S; V<> rest; // fever を考慮した実質の残りターン数 // outoput const V name{"hand", "lily", "factory", "casino", "grimoire"}; enum struct ActionType { CLICK, BUY, SELL, REINFORCE, ENHCLICK, NOTHING }; struct Action { ActionType type; int id; }; V actions(T); // status lint score; lint click_power, click_cost; V<> cnt; V power, price, cost; bool fever, sale; void convert_input() { for (int t = 0; t < T; ++t) { if (S[t] == 'F') { S[t] = 'N'; for (int i = 1; i <= 20 and t + i < T; ++i) { S[t + i] = 'F'; } t += 20; } else if (S[t] == 'S') { S[t] = 'N'; if (t + 1 < T) { S[t + 1] = 'S'; } ++t; } } rest.assign(T + 1, 0); for (int t = T - 1; t >= 0; --t) { rest[t] = rest[t + 1] + (S[t] == 'F' ? 7 : 1); } } void read_input() { cin.tie(nullptr); ios_base::sync_with_stdio(false); int _T; cin >> _T; assert(_T == T); cin >> S; assert(S.size() == T); convert_input(); } void generate_input(bool random = true) { S.assign(T, 'N'); if (random) { string bfs = "BFS"; for (int t = rng(0, 200); t < T; t += rng(100, 201)) { S[t] = bfs[rng(0, 3)]; } } convert_input(); } void write_output() { for (const Action& action : actions) { switch (action.type) { case ActionType::CLICK: cout << "click" << endl; break; case ActionType::BUY: cout << "buy " << name[action.id] << endl; break; case ActionType::SELL: cout << "sell " << name[action.id] << endl; break; case ActionType::REINFORCE: cout << "reinforce " << name[action.id] << endl; break; case ActionType::ENHCLICK: cout << "enhclick " << endl; break; case ActionType::NOTHING: cout << "nothing" << endl; break; } string s; cin >> s; assert(s == "ok"); } } void init_status() { score = 0; click_power = 1, click_cost = 15; cnt.assign(5, 0); power = { 1, 10, 120, 2'000, 25'000}; price = {150, 2'000, 30'000, 600'000, 10'000'000}; cost.resize(5); for (int id = 0; id < 5; ++id) { cost[id] = 10 * price[id]; } fever = sale = false; } bool can_buy(int id) { lint curr_price = sale ? ceilll(9 * price[id], 10) : price[id]; return score >= curr_price; } bool can_sell(int id) { return cnt[id] > 0; } bool can_reinforce(int id) { lint curr_cost = sale ? ceilll(9 * cost[id], 10) : cost[id]; return score >= curr_cost; } bool can_enhclick() { lint curr_cost = sale ? ceilll(9 * click_cost, 10) : click_cost; return score >= curr_cost; } bool can_act(const Action& action) { switch (action.type) { case ActionType::BUY: return can_buy(action.id); case ActionType::SELL: return can_sell(action.id); case ActionType::REINFORCE: return can_reinforce(action.id); case ActionType::ENHCLICK: return can_enhclick(); default: return true; } } void click() { score += click_power * (fever ? 7 : 1); } void buy(int id) { lint curr_price = sale ? ceilll(9 * price[id], 10) : price[id]; score -= curr_price; ++cnt[id]; price[id] = ceilll(6 * price[id], 5); } void sell(int id) { price[id] = 5 * price[id] / 6; --cnt[id]; score += ceilll(price[id], 4); } void reinforce(int id) { lint curr_cost = sale ? ceilll(9 * cost[id], 10) : cost[id]; score -= curr_cost; power[id] <<= 1; cost[id] *= 10; } void enhclick() { lint curr_cost = sale ? ceilll(9 * click_cost, 10) : click_cost; score -= curr_cost; click_power <<= 1; click_cost *= 10; } void act(const Action& action) { assert(can_act(action)); switch (action.type) { case ActionType::CLICK: click(); break; case ActionType::BUY: buy(action.id); break; case ActionType::SELL: sell(action.id); break; case ActionType::REINFORCE: reinforce(action.id); break; case ActionType::ENHCLICK: enhclick(); break; case ActionType::NOTHING: break; } } void produce() { for (int id = 0; id < 5; ++id) { score += power[id] * cnt[id] * (fever ? 7 : 1); } } void affect(int t) { if (S[t] == 'B') { score += ceilll(score, 100); } if (t + 1 < T) { fever = S[t + 1] == 'F'; sale = S[t + 1] == 'S'; } } void next_turn(const Action& action, int t) { fever = S[t] == 'F'; sale = S[t] == 'S'; if (can_act(action)) { act(action); } else { act({ActionType::CLICK, -1}); } produce(); affect(t); } void print_data() { init_status(); int click_cnt = 0; V<> buy_cnt(5), sell_cnt(5), reinforce_cnt(5); int enhclick_cnt = 0; lint _score, bonus_score = 0, sell_score = 0, click_score = 0; V prod_score(5); for (int t = 0; t < T; ++t) { _score = score; fever = S[t] == 'F'; sale = S[t] == 'S'; if (can_act(actions[t])) { act(actions[t]); } else { act(actions[t] = {ActionType::CLICK, -1}); } if (actions[t].type == ActionType::CLICK) click_score += score - _score; if (actions[t].type == ActionType::SELL) sell_score += score - _score; produce(); for (int id = 0; id < 5; ++id) { prod_score[id] += power[id] * cnt[id] * (fever ? 7 : 1); } _score = score; affect(t); bonus_score += score - _score; switch (actions[t].type) { case ActionType::CLICK: ++click_cnt; break; case ActionType::BUY: ++buy_cnt[actions[t].id]; cerr << "turn: " << setw(4) << t << '\t' << "buy " << name[actions[t].id] << endl; break; case ActionType::SELL: ++sell_cnt[actions[t].id]; cerr << "turn: " << setw(4) << t << '\t' << "sell " << name[actions[t].id] << endl; break; case ActionType::REINFORCE: ++reinforce_cnt[actions[t].id]; cerr << "turn: " << setw(4) << t << '\t' << "reinforce " << name[actions[t].id] << endl; break; case ActionType::ENHCLICK: ++enhclick_cnt; cerr << "turn: " << setw(4) << t << '\t' << "enhclick" << endl; break; } } cerr << "total_score: " << setw(11) << score << endl; cerr << "bonus_score: " << setw(11) << bonus_score << endl; cerr << "click_score: " << setw(11) << click_score << endl; cerr << " sell_score: " << setw(11) << sell_score << endl; for (int id = 0; id < 5; ++id) { cerr << "pr_score[" << id << "]: " << setw(11) << prod_score[id] << endl; } cerr << "click_cnt: " << click_cnt << endl; for (int id = 0; id < 5; ++id) { cerr << "buy_cnt[" << id << "]: " << buy_cnt[id] << '\t'; cerr << "sell_cnt[" << id << "]: " << sell_cnt[id] << '\t'; cerr << "reinforce_cnt[" << id << "]: " << reinforce_cnt[id] << endl; } cerr << "enhclick_cnt: " << enhclick_cnt << endl; } lint calc_power() { lint res = click_power; for (int id = 0; id < 5; ++id) { res += power[id] * cnt[id]; } return res; } int eval_act(const Action& action, int t) { auto f = [&](lint c, lint p) -> lint { return t + ceilll(c, p) + ceilll(max(c - score, 0LL), calc_power()); }; switch (action.type) { case ActionType::BUY: return f(price[action.id], power[action.id]); case ActionType::REINFORCE: return f(cost[action.id], power[action.id] * cnt[action.id]); case ActionType::ENHCLICK: return f(click_cost, click_power); default: return rest[0]; } } void first_solve() { // buy, reinforce, enhclick init_status(); for (int t = 0; t < T; ++t) { lint curr = t + rest[t], best = curr; Action curr_action = {ActionType::CLICK, -1}, best_action = curr_action; auto update = [&]() -> void { curr = eval_act(curr_action, t); if (curr < best) { best = curr; best_action = curr_action; } }; for (int id = 0; id < 5; ++id) { curr_action = {ActionType::BUY, id}; update(); if (cnt[id]) { curr_action = {ActionType::REINFORCE, id}; update(); } } curr_action = {ActionType::ENHCLICK, -1}; update(); if (can_act(best_action)) { actions[t] = best_action; } else { actions[t] = {ActionType::CLICK, -1}; } next_turn(actions[t], t); } // sell struct Status { lint score; lint click_power, click_cost; V<> cnt; V power, price, cost; bool fever, sale; }; auto copy_status = []() -> Status { return {score, click_power, click_cost, cnt, power, price, cost, fever, sale}; }; auto update_status = [](const Status& status) -> void { score = status.score; click_power = status.click_power, click_cost = status.click_cost; cnt = status.cnt; power = status.power, price = status.price, cost = status.cost; fever = status.fever, sale = status.sale; }; int Tf = T - accumulate(begin(cnt), end(cnt), 0); init_status(); for (int t = 0; t < Tf; ++t) { next_turn(actions[t], t); } auto status = copy_status(); for (int t = T - 1; t >= Tf; --t) { lint curr = 0, best = curr; Action curr_action = {ActionType::NOTHING, -1}, best_action = curr_action; auto update = [&]() -> void { update_status(status); for (int _t = Tf; _t < T; ++_t) { if (_t == t) { next_turn(curr_action, _t); } else { next_turn(actions[_t], _t); } } curr = score; if (curr > best) { best = curr; best_action = curr_action; } }; curr_action = {ActionType::CLICK, -1}; update(); for (int id = 0; id < 5; ++id) { curr_action = {ActionType::SELL, id}; update(); } actions[t] = best_action; } } void optimize(bool rev = false) { auto simulate = []() -> void { init_status(); for (int t = 0; t < T; ++t) { if (!can_act(actions[t])) { score = 0; return; } act(actions[t]); produce(); affect(t); } }; simulate(); int Tf = T - accumulate(begin(cnt), end(cnt), 0); bitset chance; for (int t = 1; t < T; ++t) { auto s = S.substr(t - 1, 2); if (s == "BN" or s == "FN" or s == "NS") { chance[t] = true; } } lint best = score; for (int t = Tf - 1; t >= 0; --t) if (actions[t].type != ActionType::CLICK) { int tb = -1; for (int _t = t + 1; _t < T and actions[_t].type == ActionType::CLICK; ++_t) { if (!chance[_t]) continue; swap(actions[t], actions[_t]); simulate(); if (score > best) { best = score; tb = _t; } swap(actions[t], actions[_t]); } if (tb != -1) { swap(actions[t], actions[tb]); } } simulate(); } int main(int argc, char* argv[]) { if (argc == 1) { read_input(); first_solve(); optimize(); write_output(); } else if (string(argv[1]) == "expt") { auto start_t = steady_clock::now(); lint total_score = 0, _total_score = 0; for (int _ = 0; _ < 32; ++_) { generate_input(); first_solve(); _total_score += score; optimize(); if (_ == 31) print_data(); total_score += score; } cerr << "Score: " << _total_score << '\n'; cerr << "Score: " << total_score << '\n'; cerr << "Time: " << duration_cast(steady_clock::now() - start_t).count() << " ms\n"; } }