#include using namespace std; #define REP(i,n) for (int i=0;i<(n);i++) #define REP2(i,m,n) for (int i=m;i<(n);i++) typedef long long ll; typedef long double ld; const int N = 10000; const int F = 5; const int MAXB = 20; const string action[5] = {"click", "buy", "sell", "reinforce", "enhclick"}; const string facility[F] = {"hand", "lily", "factory", "casino", "grimoire"}; const uint64_t productivity[F] = {1, 10, 120, 2000, 25000}; uint64_t buy_cost[F][MAXB]; uint64_t rein_cost[F][MAXB]; uint64_t click_cost[MAXB]; const int BEAM_WIDTH = 500; int prev_id[BEAM_WIDTH * N + 10]; int prev_action[BEAM_WIDTH * N + 10]; struct State { uint16_t turn; uint64_t cookies; uint16_t click_level; uint16_t facility_count[F]; uint16_t facility_level[F]; uint64_t state_score; int32_t parent_id; int8_t parent_action; State() { turn = 0; cookies = 0; click_level = 0; memset(facility_count, 0, sizeof(facility_count)); memset(facility_level, 0, sizeof(facility_level)); state_score = 0; parent_id = -1; parent_action = -1; } uint64_t eval() { uint64_t ret = 0; ret += cookies; ret += (N - turn) * (((uint64_t)(1)) << click_level); for (int i = 0; i < F; ++i) { ret += (N - turn) * productivity[i] * (((uint64_t)(1)) << facility_level[i]) * facility_count[i]; } return ret + cookies; } void harvest() { for (int i = 0; i < F; ++i) { cookies += productivity[i] * (((uint64_t)(1)) << facility_level[i]) * facility_count[i]; } } void harvest_back() { for (int i = 0; i < F; ++i) { cookies -= productivity[i] * (((uint64_t)(1)) << facility_level[i]) * facility_count[i]; } } void click() { turn += 1; cookies += ((uint64_t)(1)) << click_level; harvest(); } void click_back() { harvest_back(); cookies -= ((uint64_t)(1)) << click_level; turn -= 1; } bool buy(int f) { if (cookies < buy_cost[f][facility_count[f]]) return false; turn += 1; cookies -= buy_cost[f][facility_count[f]]; facility_count[f] += 1; harvest(); return true; } void buy_back(int f) { harvest_back(); facility_count[f] -= 1; cookies += buy_cost[f][facility_count[f]]; turn -= 1; } bool sell(int f) { if (facility_count[f] == 0) return false; turn += 1; cookies += ceil(buy_cost[f][facility_count[f]-1] / 4.0); facility_count[f] -= 1; harvest(); return true; } void sell_back(int f) { harvest_back(); facility_count[f] += 1; cookies -= ceil(buy_cost[f][facility_count[f]-1] / 4.0); turn -= 1; } bool reinforce(int f) { if (cookies < rein_cost[f][facility_level[f]]) return false; turn += 1; cookies -= rein_cost[f][facility_level[f]]; facility_level[f] += 1; harvest(); return true; } void reinforce_back(int f) { harvest_back(); facility_level[f] -= 1; cookies += rein_cost[f][facility_level[f]]; turn -= 1; } bool enhclick() { if (cookies < click_cost[click_level]) return false; turn += 1; cookies -= click_cost[click_level]; click_level += 1; harvest(); return true; } void enhclick_back() { harvest_back(); click_level -= 1; cookies += click_cost[click_level]; turn -= 1; } uint64_t eval_click() { click(); uint64_t score = eval(); click_back(); return score; } uint64_t eval_buy(int f) { if (!buy(f)) return 0; uint64_t score = eval(); buy_back(f); return score; } uint64_t eval_sell(int f) { if (!sell(f)) return 0; uint64_t score = eval(); sell_back(f); return score; } uint64_t eval_reinforce(int f) { if (!reinforce(f)) return 0; uint64_t score = eval(); reinforce_back(f); return score; } uint64_t eval_enhclick() { if (!enhclick()) return 0; uint64_t score = eval(); enhclick_back(); return score; } pair best_next_action() { // for greedy search uint64_t best_score = 0; int x = -1; int y = 0; uint64_t s; s = eval_click(); if (s > best_score) { best_score = s; x = 0; } REP(i, F) { s = eval_buy(i); if (s > best_score) { best_score = s; x = 1; y = i; } } REP(i, F) { s = eval_sell(i); if (s > best_score) { best_score = s; x = 2; y = i; } } REP(i, F) { s = eval_reinforce(i); if (s > best_score) { best_score = s; x = 3; y = i; } } s = eval_enhclick(); if (s > best_score) { best_score = s; x = 4; } return make_pair(x, y); } }; bool operator<(const State& a, const State& b) { return a.state_score < b.state_score; } void init() { buy_cost[0][0] = 150; buy_cost[1][0] = 2000; buy_cost[2][0] = 30000; buy_cost[3][0] = 600000; buy_cost[4][0] = 10000000; rein_cost[0][0] = buy_cost[0][0] * 10; rein_cost[1][0] = buy_cost[1][0] * 10; rein_cost[2][0] = buy_cost[2][0] * 10; rein_cost[3][0] = buy_cost[3][0] * 10; rein_cost[4][0] = buy_cost[4][0] * 10; click_cost[0] = 15; REP(i, F) REP(j, MAXB-1) { buy_cost[i][j+1] = ceil(6.0 * buy_cost[i][j] / 5); } REP(i, F) REP(j, MAXB-1) { rein_cost[i][j+1] = 10 * rein_cost[i][j]; } REP(j, MAXB-1) { click_cost[j+1] = click_cost[j] * 10; } } void act(int x, int y) { cout << action[x]; if (x >= 1 && x <= 3) { cout << " " << facility[y]; } cout << endl; } void greedy_search() { int hoge; string s; cin >> hoge >> s; State S; pair p; int x, y; REP(_, N) { p = S.best_next_action(); x = p.first; y = p.second; if (x == 0) { S.click(); } else if (x == 1) { S.buy(y); } else if (x == 2) { S.sell(y); } else if (x == 3) { S.reinforce(y); } else { S.enhclick(); } act(x, y); cin >> s; } } void beam_search() { int hoge; string s; cin >> hoge >> s; State S, T; priority_queue pq[2]; pq[0].push(S); int id = -1; int cur = 0, tar = 1; REP(_, N) { pq[tar] = priority_queue(); for (int k = 0; k < BEAM_WIDTH && !pq[cur].empty(); ++k) { S = pq[cur].top(); pq[cur].pop(); id += 1; prev_id[id] = S.parent_id; prev_action[id] = S.parent_action; T = S; T.parent_id = id; T.click(); T.state_score = T.eval(); T.parent_action = 0; pq[tar].push(T); T.click_back(); for (int f = 0; f < F; ++f) { if (T.buy(f)) { T.state_score = T.eval(); T.parent_action = 10 + f; pq[tar].push(T); T.buy_back(f); } } for (int f = 0; f < F; ++f) { if (T.sell(f)) { T.state_score = T.eval(); T.parent_action = 20 + f; pq[tar].push(T); T.sell_back(f); } } for (int f = 0; f < F; ++f) { if (T.reinforce(f)) { T.state_score = T.eval(); T.parent_action = 30 + f; pq[tar].push(T); T.reinforce_back(f); } } if (T.enhclick()) { T.state_score = T.eval(); T.parent_action = 40; pq[tar].push(T); T.enhclick_back(); } } cur ^= 1; tar ^= 1; } State last = pq[cur].top(); vector actions = {last.parent_action}; id = last.parent_id; while (prev_action[id] != -1) { actions.push_back(prev_action[id]); id = prev_id[id]; } for (int i = N-1; i >= 0; --i) { int x = actions[i] / 10; int y = actions[i] % 10; act(x, y); cin >> s; } } int main() { init(); beam_search(); }