//#define _CRT_SECURE_NO_WARNINGS #include "bits/stdc++.h" #include #include #include #include #ifdef _MSC_VER #include #include #include #include #include #endif using namespace std; //呪文 #define DUMPOUT cerr #define dump(...) DUMPOUT<<" ";DUMPOUT<<#__VA_ARGS__<<" :["<<__LINE__<<":"<<__FUNCTION__<<"]"< pii; typedef pair pll; typedef pair pdd; typedef pair pss; template ostream& operator << (ostream& o, const pair<_KTy, _Ty>& m) { o << "{" << m.first << ", " << m.second << "}"; return o; } template ostream& operator << (ostream& o, const map<_KTy, _Ty>& m) { if (m.empty()) { o << "{ }"; return o; } o << "{" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { o << ", " << *itr; } o << "}"; return o; } template ostream& operator << (ostream& o, const unordered_map<_KTy, _Ty>& m) { if (m.empty()) { o << "{ }"; return o; } o << "{" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { o << ", " << *itr; } o << "}"; return o; } template ostream& operator << (ostream& o, const vector<_Ty>& v) { if (v.empty()) { o << "{ }"; return o; } o << "{" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) { o << ", " << *itr; } o << "}"; return o; } template ostream& operator << (ostream& o, const set<_Ty>& s) { if (s.empty()) { o << "{ }"; return o; } o << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { o << ", " << *itr; } o << "}"; return o; } template ostream& operator << (ostream& o, const unordered_set<_Ty>& s) { if (s.empty()) { o << "{ }"; return o; } o << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { o << ", " << *itr; } o << "}"; return o; } template ostream& operator << (ostream& o, const stack<_Ty>& s) { if (s.empty()) { o << "{ }"; return o; } stack<_Ty> t(s); o << "{" << t.top(); t.pop(); while (!t.empty()) { o << ", " << t.top(); t.pop(); } o << "}"; return o; } template ostream& operator << (ostream& o, const list<_Ty>& l) { if (l.empty()) { o << "{ }"; return o; } o << "{" << l.front(); for (auto itr = ++l.begin(); itr != l.end(); ++itr) { o << ", " << *itr; } o << "}"; return o; } template istream& operator >> (istream& is, pair<_KTy, _Ty>& m) { is >> m.first >> m.second; return is; } template istream& operator >> (istream& is, vector<_Ty>& v) { for (size_t i = 0; i < v.size(); i++) is >> v[i]; return is; } namespace aux { // print tuple template struct tp { static void print(ostream& os, const Ty& v) { os << get(v) << ", "; tp::print(os, v); } }; template struct tp { static void print(ostream& os, const Ty& v) { os << get(v); } }; } template ostream& operator<<(ostream& os, const tuple& t) { os << "{"; aux::tp, 0, sizeof...(Tys) - 1>::print(os, t); os << "}"; return os; } template inline void Fill(A(&array)[N], const T &val) { std::fill((T*)array, (T*)(array + N), val); } void dump_func() { DUMPOUT << endl; } template void dump_func(Head&& head, Tail&&... tail) { DUMPOUT << head; if (sizeof...(Tail) == 0) { DUMPOUT << " "; } else { DUMPOUT << ", "; } dump_func(std::move(tail)...); } #define PI 3.14159265358979323846 #define EPS 1e-10 #define FOR(i,a,n) for(int i=(a);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define all(j) (j).begin(), (j).end() #define SZ(j) ((int)(j).size()) #define fake false struct SXor128 { unsigned x, y, z, w; SXor128() { x = 123456789; y = 362436069; z = 521288629; w = 88675123; } SXor128(int _w) { x = 123456789; y = 362436069; z = 521288629; w = _w; } void setSeed() { x = 123456789; y = 362436069; z = 521288629; w = 88675123; } void setSeed(int _w) { x = 123456789; y = 362436069; z = 521288629; w = _w; } unsigned nextUInt() { unsigned t = (x ^ (x << 11)); x = y; y = z; z = w; return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))); } unsigned nextUInt(unsigned mod) { unsigned t = (x ^ (x << 11)); x = y; y = z; z = w; w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); return w % mod; } unsigned nextUInt(unsigned l, unsigned r) { unsigned t = (x ^ (x << 11)); x = y; y = z; z = w; w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); return w % (r - l + 1) + l; } double nextDouble() { return double(nextUInt()) / UINT_MAX; } } rnd; class timer { vector timers; int n = 0; public: #ifdef _MSC_VER double limit = 9.9; #else double limit = 9.9; #endif double t = 0; timer() {} timer(int size) : timers(size) {} bool elapses() const { return time() - t > limit; } void measure() { t = time() - t; ++n; } void measure(char id) { timers[id].measure(); } void print() { if (n % 2) measure(); for (int i = 0; i < 128; ++i) { if (timers[i].n) cerr << (char)i << ' ' << timers[i].t << 's' << endl; } cerr << " " << t << 's' << endl; } static double time() { #ifdef _MSC_VER return __rdtsc() / 2.6e9; #else unsigned long long a, d; __asm__ volatile ("rdtsc" : "=a" (a), "=d" (d)); return (d << 32 | a) / 2.6e9; #endif } } timer(128); constexpr int N = 10000; string S; const vector base_cost({ 150, 2000, 30000, 600000, 10000000 }); const vector base_prod({ 1, 10, 120, 2000, 25000 }); enum EAct { CLICK, BUY, SELL, REINFORCE, ENHCLICK, NOTHING }; const vector acts({ CLICK, BUY, REINFORCE, ENHCLICK, SELL }); const map dict_acts_se({ {"click", CLICK}, {"buy", BUY}, {"sell", SELL}, {"reinforce", REINFORCE}, {"enhclick", ENHCLICK}, {"nothing", NOTHING} }); const map dict_acts_es({ {CLICK, "click"} , {BUY, "buy"}, {SELL, "sell"}, {REINFORCE, "reinforce"}, {ENHCLICK, "enhclick"}, {NOTHING, "nothing"} }); enum EBld { HAND, LILY, FACTORY, CASINO, GRIMOIRE, NONE }; const vector blds({ HAND, LILY, FACTORY, CASINO, GRIMOIRE }); const map dict_blds_se({ {"hand", HAND}, {"lily", LILY}, {"factory", FACTORY}, {"casino", CASINO}, {"grimoire", GRIMOIRE}, {"none", NONE} }); const map dict_blds_es({ {HAND, "hand"},{LILY,"lily"},{FACTORY,"factory"},{CASINO, "casino"},{GRIMOIRE,"grimoire"},{NONE,"none"} }); enum EEff { FEVER = 1, SALE = 2 }; class State { public: typedef shared_ptr StatePtr; // history : 解答出力用.あとで undo とか実装するかも char hist_act[N]; char hist_bld[N]; // ターン数 int turn; // effect のフラグ int eff_state; // effect の残りターン数 int eff_turn[3]; // 所持クッキー ll cookies; // cookies per click ll cpc; // 施設保有数 short num_blds[5]; // 基本生産性 ll prod[5]; // 購入コスト ll cost_buy[5]; // 施設強化コスト ll cost_rif[5]; // クリック強化コスト ll cost_enhclk; State() { turn = 0; cookies = 0; cpc = 1; eff_state = eff_turn[FEVER] = eff_turn[SALE] = 0; for (const auto& act : acts) { num_blds[act] = 0; prod[act] = base_prod[act]; cost_buy[act] = cost_rif[act] = base_cost[act]; cost_rif[act] *= 10; } cost_enhclk = 15; } // 行動.行動不可能(クッキー不足, 施設数 0 での売却)の場合 false が返る bool action(EAct act, EBld bld) { // 消費クッキーの計算 ll gains = 0, losts = 0, sells = 0; switch (act) { case CLICK: gains = cpc; break; case BUY: losts = cost_buy[bld]; break; case SELL: if (!num_blds[bld]) return false; // 売る施設がないよ sells = cost_buy[bld] * 5 / 6; // 現在の施設価格 sells = (sells + 3) / 4; // 25% break; case REINFORCE: losts = cost_rif[bld]; break; case ENHCLICK: losts = cost_enhclk; break; } ll diff = gains * ((eff_state & FEVER) ? 7 : 1) + sells - ((eff_state & SALE) ? (losts * 9 + 9) / 10 : losts); // クッキー不足 if (cookies + diff < 0) return false; // 各種 status の更新 switch (act) { case BUY: num_blds[bld]++; cost_buy[bld] = (cost_buy[bld] * 6 + 4) / 5; break; case SELL: num_blds[bld]--; cost_buy[bld] = cost_buy[bld] * 5 / 6; break; case REINFORCE: prod[bld] <<= 1; cost_rif[bld] *= 10; break; case ENHCLICK: cpc <<= 1; cost_enhclk *= 10; break; } // history に追加 hist_act[turn] = act; hist_bld[turn] = bld; // 行動によるクッキー総数の更新 cookies += diff; // 生産によるクッキー総数の更新 ll fever_const = (eff_state & FEVER) ? 7 : 1; for (const auto& bld : blds) cookies += num_blds[bld] * prod[bld] * fever_const; // 特殊効果のターン減少 eff_turn[FEVER]--; eff_turn[SALE]--; eff_state ^= eff_turn[FEVER] ? 0 : FEVER; eff_state ^= eff_turn[SALE] ? 0 : SALE; // 特殊効果の発動 switch (S[turn]) { case 'B': cookies = (cookies * 101 + 99) / 100; break; case 'F': eff_state |= FEVER; eff_turn[FEVER] = 20; break; case 'S': eff_state |= SALE; eff_turn[SALE] = 1; break; } // ターン数インクリメント turn++; return true; } // 十分なクッキーが集まるまで click してからコマンドを実行 bool autoplay(EAct act, EBld bld) { while (!action(act, bld)) { action(CLICK, NONE); // N ターン経過した場合は false if (turn == N) return false; } return true; } // 効率のいい ( cps/turn の最も大きな ) ものを貪欲に実行する // undo があるといいんだけど bool greedy(int turn_param) { ll cur_turn = turn; ll cur_prod_sum = 0; for (auto bld : blds) cur_prod_sum += num_blds[bld] * prod[bld]; double best_score = DBL_MIN; EAct best_act; EBld best_bld; for (auto act : { BUY, REINFORCE }) { for (auto bld : blds) { State next_state(*this); if (!next_state.autoplay(act, bld)) continue; ll next_turn = next_state.turn; if (next_turn - cur_turn > turn_param) continue; ll next_prod_sum = 0; for (auto b : blds) next_prod_sum += next_state.num_blds[b] * next_state.prod[b]; double score = double(next_prod_sum - cur_prod_sum) / (next_turn - cur_turn); if (score > best_score) { best_score = score; best_act = act; best_bld = bld; } } } if (best_score == DBL_MIN) return false; autoplay(best_act, best_bld); return true; } }; typedef shared_ptr StatePtr; StatePtr solve(const StatePtr& init_state, double timeLimit) { init_state->autoplay(ENHCLICK, NONE); init_state->autoplay(ENHCLICK, NONE); REP(i, 5) init_state->autoplay(BUY, HAND); init_state->autoplay(REINFORCE, HAND); REP(i, 2) init_state->autoplay(BUY, HAND); init_state->autoplay(ENHCLICK, NONE); ll best_cookies = init_state->cookies; StatePtr best_state = init_state; SXor128 r(init_state->cookies % 1000000007); while (timer.time() - timer.t < timeLimit) { int turn_range = 300 + r.nextUInt(400); int turn_thresh = 7000 + r.nextUInt(1500); StatePtr state(new State(*init_state)); int total_blds = 0; vector max_num_blds; ll total_sell = 0; while (state->turn < N) { if (state->turn < turn_thresh) { state->greedy(turn_range); } else { if (!total_blds) { for (auto bld : blds) { total_blds += state->num_blds[bld]; max_num_blds.push_back(state->num_blds[bld]); } } if (state->turn < 9980) state->action(CLICK, NONE); else { ll maxsell = -1; EBld maxbld = NONE; for (auto bld : blds) { if (!state->num_blds[bld]) continue; ll sell = state->cost_buy[bld] * 5 / 6; sell = (sell + 3) / 4; if (maxsell < sell) { maxsell = sell; maxbld = bld; } } if (maxsell != -1) { total_sell += maxsell; state->action(SELL, maxbld); } } } } if (state->cookies > best_cookies) { best_state = state; best_cookies = state->cookies; //cerr << best_cookies << ": " << max_num_blds << endl; } } return best_state; } //vector getAllNextStates(const StatePtr& nowState) { // vector acts({ BUY, REINFORCE, ENHCLICK }); // vector blds({ HAND, LILY, FACTORY, CASINO, GRIMOIRE }); // // vector res; // // ll now_turn = nowState->turn; // for (auto& act : acts) { // if (act != ENHCLICK) { // for (auto& bld : blds) { // StatePtr newState(new _State(*nowState)); // if (!newState->autoplay(act, bld)) continue; // if (newState->turn >= 9000 || newState->turn - now_turn > 500) continue; // res.push_back(newState); // } // } // else { // EBld bld = NONE; // StatePtr newState(new _State(*nowState)); // if (!newState->autoplay(act, bld)) continue; // if (newState->turn >= 9000 || newState->turn - now_turn > 500) continue; // res.push_back(newState); // } // } // return res; //} string testcase(unsigned seed) { rnd.setSeed(seed); REP(i, 100) rnd.nextUInt(); int range_min = 0, range_max = 199; string S(N, 'N'); while (range_min < N) { int idx = rnd.nextUInt(range_min, range_max); if (idx >= N) break; int kind = rnd.nextUInt(3); if (kind == 0) S[idx] = 'B'; else if (kind == 1) S[idx] = 'F'; else S[idx] = 'S'; range_min = idx + 100; range_max = idx + 200; } return S; } //#ifdef _MSC_VER //typedef struct SMouseParams { // int event, x, y, flags; // SMouseParams() {} // SMouseParams(int event, int x, int y, int flags) : event(event), x(x), y(y), flags(flags) {} //}*SMouseParamsPtr; // //void mouse_callback(int event, int x, int y, int flags, void* params) { // SMouseParamsPtr mp = static_cast(params); // mp->event = event; // mp->x = x; // mp->y = y; // mp->flags = flags; //} // //struct Button { // //int x1, y1, x2, y2; // cv::Rect roi; // EAct act; // EBld bld; // string text; // cv::Mat_ img; // // Button(int x1, int y1, int x2, int y2, EAct act, EBld bld, string text) // : roi(x1, y1, x2 - x1, y2 - y1), act(act), bld(bld), text(text) // { // img = cv::Mat_(y2 - y1, x2 - x1, cv::Vec3b(255, 255, 255)); // cv::rectangle(img, cv::Rect(0, 0, x2 - x1, y2 - y1), cv::Scalar(0, 0, 0), 3, cv::LINE_AA); // cv::putText(img, text, cv::Point(20, y2 - y1 - 32), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0, 0, 0), 1, cv::LINE_AA); // //ll diff = state->diff(act, bld); // //cv::putText(img, to_string(abs(diff)), cv::Point(20, y2 - y1 - 8), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0, 0, 0), 1, cv::LINE_AA); // } //}; // //void play(StatePtr state) { // // int W = 500; // int H = 500; // cv::Mat_ board(H, W, cv::Vec3b(255, 255, 255)); // // vector