#301157 (C++11) No.5003 物理好きクリッカー

• 問題: No.5003 物理好きクリッカー
• ユーザー: komori3
• 提出日時: 2018-12-03 18:36:07
• 言語: C++11 (gcc 11.4.0)
• 結果: TLE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 21,249 bytes
• コンパイル時間: 3,035 ms
• 実行使用メモリ: 14,664 KB
• スコア: 0
• 最終ジャッジ日時: 2021-07-19 08:13:38
• 合計ジャッジ時間: 351,867 ms
• ジャッジサーバーID （参考情報）: judge11 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	TLE	-
testcase_01	TLE	-
testcase_02	TLE	-
testcase_03	TLE	-
testcase_04	TLE	-
testcase_05	TLE	-
testcase_06	TLE	-
testcase_07	TLE	-
testcase_08	TLE	-
testcase_09	TLE	-
testcase_10	TLE	-
testcase_11	TLE	-
testcase_12	TLE	-
testcase_13	TLE	-
testcase_14	TLE	-
testcase_15	TLE	-
testcase_16	TLE	-
testcase_17	TLE	-
testcase_18	TLE	-
testcase_19	TLE	-
testcase_20	TLE	-
testcase_21	TLE	-
testcase_22	TLE	-
testcase_23	TLE	-
testcase_24	TLE	-
testcase_25	TLE	-
testcase_26	TLE	-
testcase_27	TLE	-
testcase_28	TLE	-
testcase_29	TLE	-
testcase_30	TLE	-
testcase_31	TLE	-

コンパイルメッセージ

main.cpp: In function ‘void optimal(const StatePtr&, int)’:
main.cpp:183:29: warning: ‘best_bld’ may be used uninitialized in this function [-Wmaybe-uninitialized]
    losts = cost_purchase[bld];
            ~~~~~~~~~~~~~~~~~^
main.cpp:328:9: note: ‘best_bld’ was declared here
  EBuild best_bld;
         ^~~~~~~~

ソースコード

//#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
#include <iostream>
#include <random>
#include <unordered_map>
#include <unordered_set>
#ifdef _MSC_VER
#include <opencv2/core.hpp>
#include <opencv2/highgui.hpp>
#include <opencv2/imgproc.hpp>
#include <ppl.h>
#endif

using namespace std;

//呪文
#define DUMPOUT cerr
#define dump(...) DUMPOUT<<"  ";DUMPOUT<<#__VA_ARGS__<<" :["<<__LINE__<<":"<<__FUNCTION__<<"]"<<endl;DUMPOUT<<"    ";dump_func(__VA_ARGS__)

typedef unsigned uint; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; typedef pair<string, string> pss;
template <typename _KTy, typename _Ty> ostream& operator << (ostream& o, const pair<_KTy, _Ty>& m) { o << "{" << m.first << ", " << m.second << "}"; return o; }
template <typename _KTy, typename _Ty> 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 <typename _KTy, typename _Ty> 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 <typename _Ty> 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 <typename _Ty> 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 <typename _Ty> 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 <typename _Ty> 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 <typename _Ty> 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 <typename _KTy, typename _Ty> istream& operator >> (istream& is, pair<_KTy, _Ty>& m) { is >> m.first >> m.second; return is; }
template <typename _Ty> 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<typename Ty, unsigned N, unsigned L> struct tp { static void print(ostream& os, const Ty& v) { os << get<N>(v) << ", "; tp<Ty, N + 1, L>::print(os, v); } };
	template<typename Ty, unsigned N> struct tp<Ty, N, N> { static void print(ostream& os, const Ty& v) { os << get<N>(v); } };
}

template<typename... Tys> ostream& operator<<(ostream& os, const tuple<Tys...>& t) { os << "{"; aux::tp<tuple<Tys...>, 0, sizeof...(Tys) - 1>::print(os, t); os << "}"; return os; }

template<typename A, size_t N, typename T> inline void Fill(A(&array)[N], const T &val) { std::fill((T*)array, (T*)(array + N), val); }

void dump_func() { DUMPOUT << endl; }
template <class Head, class... Tail> 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<timer> 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;

enum EAct { CLICK, BUY, SELL, REINFORCE, ENHCLICK, NOTHING };
const map<string, EAct> dict_acts({ {"click", CLICK}, {"buy", BUY}, {"sell", SELL}, {"reinforce", REINFORCE}, {"enhclick", ENHCLICK}, {"nothing", NOTHING} });
const map<EAct, string> dict_acts_inv({ {CLICK, "click"} , {BUY, "buy"}, {SELL, "sell"}, {REINFORCE, "reinforce"}, {ENHCLICK, "enhclick"}, {NOTHING, "nothing"} });

enum EBuild { HAND, LILY, FACTORY, CASINO, GRIMOIRE, NONE };
const map<string, EBuild> dict_blds({ {"hand", HAND}, {"lily", LILY}, {"factory", FACTORY}, {"casino", CASINO}, {"grimoire", GRIMOIRE}, {"none", NONE} });
const map<EBuild, string> dict_blds_inv({ {HAND, "hand"},{LILY,"lily"},{FACTORY,"factory"},{CASINO, "casino"},{GRIMOIRE,"grimoire"},{NONE,"none"} });

const vector<ll> base_cost({ 150, 2000, 30000, 600000, 10000000 });
const vector<ll> base_productivity({ 1, 10, 120, 2000, 25000 });

enum EEffect { FEVER = 1, SALE = 2 };


class State {
public:
	char hist_act[N];
	char hist_bld[N];

	int turn;

	int effects_turn[3];
	int effects_state;

	ll total_cookies;
	ll cookies_per_click;

	short blds_count[5];
	ll productivity[5];
	ll cost_purchase[5];
	ll cost_reinforce[5];
	ll cost_enhclick;

	State() {
		turn = 0;
		total_cookies = 0;
		cookies_per_click = 1;
		effects_state = effects_turn[FEVER] = effects_turn[SALE] = 0;
		REP(i, 5) {
			blds_count[i] = 0;
			productivity[i] = base_productivity[i];
			cost_purchase[i] = cost_reinforce[i] = base_cost[i];
			cost_reinforce[i] *= 10;
		}
		cost_enhclick = 15;
	}

	// action した際の cookie の変化
	ll diff(EAct act, EBuild bld) {
		ll gains = 0, losts = 0, sells = 0;
		switch (act) {
		case CLICK:
			gains = cookies_per_click;
			break;
		case BUY:
			losts = cost_purchase[bld];
			break;
		case SELL:
			if (blds_count[bld]) {
				sells = cost_purchase[bld] * 5 / 6;
				sells = (sells + 3) / 4;
			}
			break;
		case REINFORCE:
			losts = cost_reinforce[bld];
			break;
		case ENHCLICK:
			losts = cost_enhclick;
			break;
		}
		return gains * ((effects_state & FEVER) ? 7 : 1) + sells - ((effects_state & SALE) ? (losts * 9 + 9) / 10 : losts);
	}

	// action
	void action(EAct act, EBuild bld, ll difference) {
		assert(total_cookies + difference >= 0);
		//dump(turn, act, bld, difference);
		switch (act)
		{
		case BUY:
			blds_count[bld]++;
			cost_purchase[bld] = (cost_purchase[bld] * 6 + 4) / 5;
			break;
		case SELL:
			if (blds_count[bld]) {
				blds_count[bld]--;
				cost_purchase[bld] = cost_purchase[bld] * 5 / 6;
			}
			break;
		case REINFORCE:
			productivity[bld] <<= 1;
			cost_reinforce[bld] *= 10;
			break;
		case ENHCLICK:
			cookies_per_click <<= 1;
			cost_enhclick *= 10;
			break;
		}
		hist_act[turn] = act;
		hist_bld[turn] = bld;

		total_cookies += difference;

		ll fever_const = (effects_state & FEVER) ? 7 : 1;
		REP(i, 5) total_cookies += blds_count[i] * productivity[i] * fever_const;

		// 特殊効果ターン減少
		effects_turn[FEVER]--;
		effects_turn[SALE]--;
		effects_state ^= effects_turn[FEVER] ? 0 : FEVER;
		effects_state ^= effects_turn[SALE] ? 0 : SALE;

		// 特殊効果
		if (S[turn] == 'B') // Bonus
			total_cookies = (total_cookies * 101 + 99) / 100;
		else if (S[turn] == 'F') {
			effects_state |= FEVER;
			effects_turn[FEVER] = 20;
		}
		else if (S[turn] == 'S') {
			effects_state |= SALE;
			effects_turn[SALE] = 1;
		}

		turn++;
	}

	// コマンドを実行するだけのクッキーが集まるまでオートクリック
	bool autoplay(EAct act, EBuild bld) {
		ll difference = diff(act, bld);
		while (total_cookies + difference < 0) {
			ll d = diff(CLICK, NONE);
			action(CLICK, NONE, d);
			if (turn == N) return false;
			difference = diff(act, bld);
		}
		action(act, bld, difference);
		return true;
	}

	void command() {
		string act, bld;
		cout << "input: ";
		cin >> act;
		if (dict_acts.find(act) == dict_acts.end()) {
			cerr << "invalid act." << endl;
			return;
		}

		EAct eact = dict_acts.at(act);

		if (act == "buy" || act == "sell" || act == "reinforce") {
			cin >> bld;
			if (dict_blds.find(bld) == dict_blds.end()) {
				cerr << "invalid bld." << endl;
				return;
			}

			EBuild ebld = dict_blds.at(bld);
			ll d = diff(eact, ebld);
			if (total_cookies + d < 0) {
				cerr << "money shortage." << endl;
				return;
			}
			action(eact, ebld, d);
		}
		else {
			ll d = diff(eact, NONE);
			if (total_cookies + d < 0) {
				cerr << "money shortage." << endl;
				return;
			}
			action(eact, NONE, d);
		}

		cerr << "turn: " << turn << endl;
		cerr << "cookies: " << total_cookies << endl;
		cerr << "cps: " << cookies_per_click << endl;
		for (int i = 0; i < 5; i++) {
			cerr << "number of " + dict_blds_inv.at(static_cast<EBuild>(i)) + ": " << blds_count[i] << endl;
			cerr << "productivity of " + dict_blds_inv.at(static_cast<EBuild>(i)) + ": " << productivity[i] << endl;
			cerr << "purchase cost of " + dict_blds_inv.at(static_cast<EBuild>(i)) + ": " << cost_purchase[i] << endl;
			cerr << "reinforce cost of " + dict_blds_inv.at(static_cast<EBuild>(i)) + ": " << cost_reinforce[i] << endl << endl;
		}
		cerr << "enhclick cost: " << cost_enhclick << endl << endl;
		cerr << "fever: " << effects_turn[FEVER] << endl;
		cerr << "sale: " << effects_turn[SALE] << endl << endl;
	}
};

typedef shared_ptr<State> StatePtr;

void optimal(const StatePtr& state, int turn_param = 500) {
	ll cur_turn = state->turn;
	ll cur_productivity = 0;
	REP(i, 5) cur_productivity += state->blds_count[i] * state->productivity[i];
	
	// 効率のいい ( cps/turn の最も大きな ) ものを貪欲に実行する
	double best_score = -1;
	EAct best_act;
	EBuild best_bld;

	EAct act = BUY;
	REP(i, 5) {
		StatePtr next_state(new State(*state));
		if (!next_state->autoplay(act, EBuild(i))) continue;;
		ll next_turn = next_state->turn;
		if (next_turn - cur_turn > turn_param) continue;
		ll next_productivity = 0;
		REP(j, 5) next_productivity += next_state->blds_count[j] * next_state->productivity[j];
		double score = double(next_productivity - cur_productivity) / (next_turn - cur_turn);
		if (score > best_score) {
			best_score = score;
			best_act = act;
			best_bld = EBuild(i);
		}
	}
	act = REINFORCE;
	REP(i, 5) {
		StatePtr next_state(new State(*state));
		if (!next_state->autoplay(act, EBuild(i))) continue;;
		ll next_turn = next_state->turn;
		if (next_turn - cur_turn > turn_param) continue;
		ll next_productivity = 0;
		REP(j, 5) next_productivity += next_state->blds_count[j] * next_state->productivity[j];
		double score = double(next_productivity - cur_productivity) / (next_turn - cur_turn);
		if (score > best_score) {
			best_score = score;
			best_act = act;
			best_bld = EBuild(i);
		}
	}
	assert(best_score != -1);

	state->autoplay(best_act, best_bld);
}

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);

	StatePtr best_state = init_state;
	ll best_score = init_state->total_cookies;

	SXor128	r(init_state->total_cookies % 1000000007);
	REP(i, 100) r.nextUInt();

	while (timer.time() - timer.t < timeLimit) {
		int turn_range = 300 + r.nextUInt(400);
		int turn_thresh = 6500 + r.nextUInt(2000);

		StatePtr state(new State(*init_state));

		while (state->turn < N) {
			if (state->turn < turn_thresh) {
				optimal(state);
			}
			else if (state->turn < 9950) {
				if (!state->autoplay(CLICK, NONE)) break;
			}
			else if (state->turn < N) {
				ll maxsell = -1;
				EBuild maxbld = NONE;
				for (int i = 4; i >= 0; i--) {
					ll d = state->diff(SELL, EBuild(i));
					if (maxsell < d) {
						maxsell = d;
						maxbld = EBuild(i);
					}
				}
				if (maxsell != -1) {
					state->action(SELL, maxbld, maxsell);
				}
			}
		}

		if (state->total_cookies > best_score) {
			best_state = state;
			best_score = state->total_cookies;
			//cerr << best_score << endl;
		}
	}
	return best_state;
}

class Cmp {
public:
	bool operator() (const StatePtr& t1, const StatePtr& t2) {
		return t1->total_cookies < t2->total_cookies;
	}
};

typedef priority_queue<StatePtr, vector<StatePtr>, Cmp> Heap;

void addAllNextStates(Heap& heap, const StatePtr& nowState) {
	for (int i = 0; i < 5; i++) {
		EAct act = static_cast<EAct>(i);
		if (1 <= i && i <= 3) {
			for (int j = 0; j < 5; j++) {
				EBuild bld = static_cast<EBuild>(j);
				ll difference = nowState->diff(act, bld);
				if (nowState->total_cookies + difference < 0) continue;
				StatePtr newState(new State(*nowState));
				newState->action(act, bld, difference);
				heap.push(newState);
			}
		}
		else {
			EBuild bld = NONE;
			ll difference = nowState->diff(act, bld);
			if (nowState->total_cookies + difference >= 0) {
				StatePtr newState(new State(*nowState));
				newState->action(act, bld, difference);
				heap.push(newState);
			}
		}
	}
}

StatePtr beam_search(const shared_ptr<State>& firstState) {

	Heap nowStates;
	nowStates.push(firstState);
	
	int width = 1000;
	for (int t = 0; t < 10000; t++) {
		cerr << t << ": " << nowStates.top()->total_cookies << endl;
		Heap nextStates;
		for (int i = 0; i < width; i++) {
			if (nowStates.empty()) break;
			const StatePtr& nowState = nowStates.top();
			addAllNextStates(nextStates, nowState);
			nowStates.pop();
		}
		nowStates = nextStates;
	}
	return nowStates.top();
}


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<SMouseParamsPtr>(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;
	EBuild bld;
	string text;
	cv::Mat_<cv::Vec3b> img;

	Button(int x1, int y1, int x2, int y2, EAct act, EBuild bld, string text)
		: roi(x1, y1, x2 - x1, y2 - y1), act(act), bld(bld), text(text) 
	{
		img = cv::Mat_<cv::Vec3b>(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_<cv::Vec3b> board(H, W, cv::Vec3b(255, 255, 255));

	vector<Button> buttons;	
	buttons.emplace_back(0, 0, 250, 250, CLICK, NONE, "cookie");
	buttons.emplace_back(0, 250, 250, 500, ENHCLICK, NONE, "enhance click");
	for (int i = 0; i < 5; i++) {
		buttons.emplace_back(250, 100 * i, 500, 100 * i + 50, BUY, EBuild(i), "buy " + dict_blds_inv.at(EBuild(i)));
		buttons.emplace_back(250, 100 * i + 50, 500, 100 * i + 100, REINFORCE, EBuild(i), "reinforce " + dict_blds_inv.at(EBuild(i)));
	}

	for (int i = 0; i < buttons.size(); i++) {
		cv::Mat img_roi = board(buttons[i].roi);
		//dump(buttons[i].roi, buttons[i].img.size(), board.size());
		buttons[i].img.copyTo(img_roi);
	}

	cv::String winname = "window";
	cv::namedWindow(winname);
	cv::imshow(winname, board);
	cv::waitKey(15);

	SMouseParamsPtr mp(new SMouseParams(0, 0, 0, 0));
	cv::setMouseCallback(winname, mouse_callback, mp);

	state->autoplay(ENHCLICK, NONE);
	state->autoplay(ENHCLICK, NONE);
	REP(i, 5) state->autoplay(BUY, HAND);
	state->autoplay(REINFORCE, HAND);
	REP(i, 2) state->autoplay(BUY, HAND);
	state->autoplay(ENHCLICK, NONE);


	int key;
	do {
		cv::Mat_<cv::Vec3b> cur_board = board.clone();

		cv::Point p(mp->x, mp->y);
		
		EAct act_selected;
		EBuild bld_selected;
		ll diff_selected;
		ll fever_const = (state->effects_state & FEVER) ? 7 : 1;
		bool sale = state->effects_state & SALE;
		ll total_cps = 0;
		for (int i = 0; i < buttons.size(); i++) {
			EAct act = buttons[i].act;
			EBuild bld = buttons[i].bld;
			ll diff = state->diff(act, bld);
			cv::putText(cur_board(buttons[i].roi), to_string(abs(diff)), cv::Point(20, buttons[i].roi.height - 8), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0, 0, 0), 1, cv::LINE_AA);
			if (act == BUY) {
				ll sum_cps = state->blds_count[bld] * state->productivity[bld] * fever_const;
				total_cps += sum_cps;
				cv::putText(cur_board(buttons[i].roi), to_string(state->blds_count[bld]),
					cv::Point(200, buttons[i].roi.height - 32), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0, 0, 0), 1, cv::LINE_AA);
				cv::putText(cur_board(buttons[i].roi), to_string(sum_cps),
					cv::Point(150, buttons[i].roi.height - 8), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0, 0, 0), 1, cv::LINE_AA);
			}
			if (buttons[i].roi.contains(p)) {
				act_selected = buttons[i].act;
				bld_selected = buttons[i].bld;
				diff_selected = diff;
			}
		}

		cv::putText(cur_board, "turn: " + to_string(state->turn), cv::Point(20, 20), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0, 0, 0), 1, cv::LINE_AA);
		cv::putText(cur_board, "cps: " + to_string(total_cps), cv::Point(20, 40), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0, 0, 0), 1, cv::LINE_AA);

		cv::putText(cur_board(buttons[0].roi), to_string(state->total_cookies), cv::Point(20, 100), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0,0,0), 1, cv::LINE_AA);

		//cv::imshow(winname, cur_board);
		//key = cv::waitKey(15);

		if (/*key == 'a'*/ state->turn < 8000) {
			optimal(state);
			// 足りなかったら足りるまでクッキーを焼き続ける
			//if(!state->autoplay(act_selected, bld_selected)) return;
		}
		else if (/*key == 'c'*/ state->turn < 9950) {
			if(!state->autoplay(CLICK, NONE)) return;
		}
		else if(state->turn < 10000) {
			ll maxsell = -1;
			EBuild maxbld = NONE;
			for (int i = 4; i >= 0; i--) {
				ll d = state->diff(SELL, EBuild(i));
				if (maxsell < d) {
					maxsell = d;
					maxbld = EBuild(i);
				}
			}
			if (maxsell != -1) {
				state->action(SELL, maxbld, maxsell);
			}
		}
		else {
			key = 27;
		}

	} while (key != 27);
}
#endif

int _main() {
	timer.measure();

	cin.tie(0);
	ios::sync_with_stdio(false);

	REP(i, 100) rnd.nextUInt();

	ll total = 0;
	for (int i = 0; i < 32; i++) {
		double start = timer.time() - timer.t;
		double end = start + 9.0;
		unsigned seed = rnd.nextUInt();
		
		S = testcase(seed);
		StatePtr state(new State);

		state = solve(state, end);

		cerr << "seed " << seed << ": " << state->total_cookies << endl;
		total += state->total_cookies;
	}
	cerr << "total: " << total << endl;

	return 0;
}

int main() {
	timer.measure();

	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int buf;
	cin >> buf >> S;
	//S = testcase(0);

	StatePtr state(new State);

	state = solve(state, 9.0);

	string retval;
	for (int i = 0; i < state->turn; i++) {
		EAct act = EAct(state->hist_act[i]);
		EBuild bld = EBuild(state->hist_bld[i]);
		cout << dict_acts_inv.at(act);
		if (bld != NONE) cout << " " << dict_blds_inv.at(bld);
		cout << endl;
		cin >> retval;
		if (retval != "ok") return -1;
	}

	return 0;
}