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

• 問題: No.5003 物理好きクリッカー
• ユーザー: komori3
• 提出日時: 2018-12-08 06:43:48
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 452 ms / 10,000 ms
• コード長: 27,735 bytes
• コンパイル時間: 4,315 ms
• 実行使用メモリ: 21,984 KB
• スコア: 303,390,362,876
• 平均クエリ数: 10000.00
• 最終ジャッジ日時: 2021-07-19 09:08:48
• 合計ジャッジ時間: 20,167 ms
• ジャッジサーバーID （参考情報）: judge15 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	437 ms; 21,348 KB
testcase_01	AC	374 ms; 21,864 KB
testcase_02	AC	388 ms; 21,852 KB
testcase_03	AC	371 ms; 21,492 KB
testcase_04	AC	386 ms; 21,984 KB
testcase_05	AC	373 ms; 21,696 KB
testcase_06	AC	378 ms; 21,672 KB
testcase_07	AC	369 ms; 21,732 KB
testcase_08	AC	374 ms; 21,864 KB
testcase_09	AC	365 ms; 21,540 KB
testcase_10	AC	417 ms; 21,888 KB
testcase_11	AC	405 ms; 21,852 KB
testcase_12	AC	394 ms; 21,360 KB
testcase_13	AC	369 ms; 21,336 KB
testcase_14	AC	407 ms; 21,828 KB
testcase_15	AC	378 ms; 21,348 KB
testcase_16	AC	396 ms; 21,852 KB
testcase_17	AC	351 ms; 21,540 KB
testcase_18	AC	395 ms; 21,660 KB
testcase_19	AC	392 ms; 21,528 KB
testcase_20	AC	399 ms; 21,336 KB
testcase_21	AC	371 ms; 21,528 KB
testcase_22	AC	368 ms; 21,516 KB
testcase_23	AC	381 ms; 21,528 KB
testcase_24	AC	452 ms; 21,504 KB
testcase_25	AC	408 ms; 21,516 KB
testcase_26	AC	376 ms; 21,660 KB
testcase_27	AC	412 ms; 21,696 KB
testcase_28	AC	408 ms; 21,516 KB
testcase_29	AC	398 ms; 21,300 KB
testcase_30	AC	435 ms; 21,648 KB
testcase_31	AC	441 ms; 21,864 KB

コンパイルメッセージ

main.cpp: メンバ関数 ‘bool State::greedy()’ 内:
main.cpp:450:32: 警告: ‘cost’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
  450 |   ll t = turn + max(0LL, (cost - cookies + cur_prod - 1) / cur_prod);
      |                           ~~~~~^~~~~~~~~
main.cpp:433:6: 備考: ‘cost’ はここで定義されています
  433 |   ll cost, delta;
      |      ^~~~
main.cpp:349:17: 警告: ‘best_bld’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
  349 |   while (!action(act, bld)) {
      |           ~~~~~~^~~~~~~~~~
main.cpp:474:8: 備考: ‘best_bld’ はここで定義されています
  474 |   EBld best_bld;
      |        ^~~~~~~~
main.cpp:349:17: 警告: ‘best_act’ はこの関数内初期化されずに使用されるかもしれません [-Wmaybe-uninitialized]
  349 |   while (!action(act, bld)) {
      |           ~~~~~~^~~~~~~~~~
main.cpp:473:8: 備考: ‘best_act’ はここで定義されています
  473 |   EAct best_act;
      |        ^~~~~~~~

ソースコード

//#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
#include <iostream>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <array>
#ifdef _MSC_VER
//#include <opencv2/core.hpp>
//#include <opencv2/highgui.hpp>
//#include <opencv2/imgproc.hpp>
#include <ppl.h>
//#include <windows.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;

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

enum EAct { CLICK, BUY, SELL, REINFORCE, ENHCLICK, NOTHING };
const vector<EAct> acts({ CLICK, BUY, REINFORCE, ENHCLICK, SELL });
const map<string, EAct> dict_acts_se({ { "click", CLICK },{ "buy", BUY },{ "sell", SELL },{ "reinforce", REINFORCE },{ "enhclick", ENHCLICK },{ "nothing", NOTHING } });
const map<EAct, string> 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<EBld> blds({ HAND, LILY, FACTORY, CASINO, GRIMOIRE });
const map<string, EBld> dict_blds_se({ { "hand", HAND },{ "lily", LILY },{ "factory", FACTORY },{ "casino", CASINO },{ "grimoire", GRIMOIRE },{ "none", NONE } });
const map<EBld, string> 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<State> StatePtr;

	shared_ptr<bitset<N>> bonus;
	shared_ptr<bitset<N>> fever;
	shared_ptr<bitset<N>> sale;
	shared_ptr<array<int, N>> fcum;

	// history : 解答出力用．あとで undo とか実装するかも
	array<char, N> hist_act;
	array<char, N> hist_bld;

	// ターン数
	int turn;

	// 所持クッキー
	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(const string& S) {
		bitset<N> b, f, s;
		array<int, N> fc;
		REP(i, N) fc[i] = 0;
		REP(i, N) {
			switch (S[i])
			{
			case 'B':
				b[i] = true;
				break;
			case 'F':
				for (int j = 1; j <= 20 && i + j < N; j++) {
					f[i + j] = true;
					fc[i + j] = 1;
				}
				break;
			case 'S':
				if(i + 1 < N) s[i + 1] = true;
				break;
			}
		}
		for (int i = N - 2; i >= 0; i--) fc[i] += fc[i + 1];
		fcum = shared_ptr<array<int, N>>(new array<int, N>(fc));
		
		bonus = shared_ptr<bitset<N>>(new bitset<N>(b));
		fever = shared_ptr<bitset<N>>(new bitset<N>(f));
		sale = shared_ptr<bitset<N>>(new bitset<N>(s));

		turn = 0;
		cookies = 0;
		cpc = 1;
		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) {
		if (turn == N) return false;

		// 消費クッキーの計算
		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 * ((*fever)[turn] ? 7 : 1) + sells - ((*sale)[turn] ? (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;

		// 生産によるクッキー総数の更新
		for (const auto& bld : blds) cookies += num_blds[bld] * prod[bld] * ((*fever)[turn] ? 7 : 1);

		// ボーナスの発動
		if ((*bonus)[turn]) cookies = (cookies * 101 + 99) / 100;

		// ターン数インクリメント
		turn++;
		return true;
	}

	bool undo() {
		turn--;
		if ((*bonus)[turn]) cookies = cookies * 100 / 101;
		for (const auto& bld : blds) cookies -= num_blds[bld] * prod[bld] * ((*fever)[turn] ? 7 : 1);

		EAct act = EAct(hist_act[turn]);
		EBld bld = EBld(hist_bld[turn]);

		switch (act)
		{
		case BUY:
			cost_buy[bld] = cost_buy[bld] * 5 / 6;
			num_blds[bld]--;
			break;
		case SELL:
			cost_buy[bld] = (cost_buy[bld] * 6 + 4) / 5;
			num_blds[bld]++;
			break;
		case REINFORCE:
			cost_rif[bld] /= 10;
			prod[bld] >>= 1;
			break;
		case ENHCLICK:
			cost_enhclk /= 10;
			cpc >>= 1;
			break;
		}

		ll gains = 0, losts = 0, sells = 0;
		switch (act)
		{
		case CLICK: gains = cpc; break;
		case BUY: losts = cost_buy[bld]; break;
		case SELL:
			sells = cost_buy[bld] * 5 / 6;
			sells = (sells + 3) / 4;
			break;
		case REINFORCE: losts = cost_rif[bld]; break;
		case ENHCLICK: losts = cost_enhclk; break;
		}
		ll diff = ((*sale)[turn] ? (losts * 9 + 9) / 10 : losts) - sells - gains * ((*fever)[turn] ? 7 : 1);

		cookies += diff;
		assert(cookies >= 0);

		return true;
	}

	// 巻き戻し
	void rewind(int t) {
		// 履歴以外を初期化
		turn = 0;
		cookies = 0;
		cpc = 1;
		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;

		// t ステップ進む
		for (int i = 0; i < t; i++)
			action(EAct(hist_act[i]), EBld(hist_bld[i]));
	}

	// 十分なクッキーが集まるまで click してからコマンドを実行
	bool autoplay(EAct act, EBld bld) {
		int cur_turn = turn;
		while (!action(act, bld)) {
			action(CLICK, NONE);
			// turn_range ターン経過した場合は false
			if (turn >= N) return false;
		}
		return true;
	}

	// 最も高い施設を売却する
	bool sell_highest() {
		ll max_sell = INT64_MIN;
		EBld max_bld = NONE;
		for (auto bld : blds) {
			if (!num_blds[bld]) continue;
			ll sell = cost_buy[bld] * 5 / 6;
			sell = (sell + 3) / 4;
			if (max_sell < sell) {
				max_sell = sell;
				max_bld = bld;
			}
		}
		if (max_bld == NONE) return false;
		action(SELL, max_bld);
		return true;
	}

	// n ターンにわたって生産量の低い施設から売却していく
	bool sell_blds(int n) {
		vector<pll> candidates; // (prod, bld)
		ll cost_cpy[5], num_cpy[5];
		REP(i, 5) {
			cost_cpy[i] = cost_buy[i];
			num_cpy[i] = num_blds[i];
		}
		for (int i = 0; i < n; i++) {
			ll max_sell = INT64_MIN;
			EBld max_bld = NONE;
			for (auto bld : blds) {
				if (!num_cpy[bld]) continue;
				ll sell = cost_cpy[bld] * 5 / 6;
				sell = (sell + 3) / 4;
				if (max_sell < sell) {
					max_sell = sell;
					max_bld = bld;
				}
			}
			if (max_bld == NONE) return false;
			candidates.emplace_back(prod[max_bld], max_bld);
			cost_cpy[max_bld] = cost_cpy[max_bld] * 5 / 6;
			num_cpy[max_bld]--;
		}
		sort(all(candidates));
		for (auto& e : candidates)
			action(SELL, EBld(e.second));

		return true;
	}

	ll prod_sum() {
		ll res = 0;
		for (auto bld : blds)
			res += prod[bld] * num_blds[bld];
		res += cpc;
		return res;
	}

	ll pseudo_score() {
		ll res = 0;
		StatePtr s(new State(*this));
		s->rewind(0);

		for (int t = 0; t < N; t++) {
			EAct act = EAct(hist_act[t]);
			EBld bld = EBld(hist_bld[t]);
			ll prev_prod = s->prod_sum();
			res += s->pseudo_score(act, bld);
			s->action(act, bld);
		}

		return res;
	}

	ll pseudo_score(EAct act, EBld bld) {
		ll cur_prod = prod_sum();
		ll cost, delta;
		if (act == BUY) {
			cost = cost_buy[bld];
			delta = prod[bld];
		}
		else if (act == REINFORCE) {
			cost = cost_rif[bld];
			delta = prod[bld] * num_blds[bld];
		}
		else if (act == ENHCLICK) {
			cost = cost_enhclk;
			delta = cpc;
		}
		//ll buy = cost_buy[bld];
		//ll rif = cost_rif[bld];
		//ll enh = cost_enhclk;
		ll next_prod = cur_prod + delta;
		ll t = turn + max(0LL, (cost - cookies + cur_prod - 1) / cur_prod);
		if (t >= N) return INT64_MIN;
		ll d = 0;
		if (act == BUY) {
			d = (next_prod - cur_prod) * (N - t + 6 * fcum->at(t)) - 3 * cost / 4;
		}
		else if (act == REINFORCE) {
			d = (next_prod - cur_prod) * (N - t + 6 * fcum->at(t)) - cost;
		}
		else if (act == ENHCLICK) {
			d = (next_prod - cur_prod) * (N - t + 6 * fcum->at(t)) - cost;
		}
		return d;
	}

	// 効率のいい ( Log(1+ΔCpT/CpT)/T の最も大きな ) ものを貪欲に実行する
	// https://ita.hatenadiary.jp/entry/20130920/p1
	// undo があるといいんだけど
	bool greedy() {
		ll cur_turn = turn;
		ll cur_prod_sum = prod_sum();

		double best_score = DBL_MIN;
		EAct best_act;
		EBld best_bld;

		for (auto act : { BUY, REINFORCE, ENHCLICK }) {
			auto bs = (act == ENHCLICK ? vector<EBld>({ NONE }) : blds);
			for (auto bld : bs) {
				if (pseudo_score(act, bld) < 0) continue;
				//dump(dict_acts_es.at(act), dict_blds_es.at(bld), pseudo_score(act, bld));
				State next_state(*this);
				if (!next_state.autoplay(act, bld)) continue;
				ll next_turn = next_state.turn;
				ll next_prod_sum = next_state.prod_sum();
				double score = log(1 + double(next_prod_sum - cur_prod_sum) / next_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<State> StatePtr;

StatePtr solve(const StatePtr& init_state) {
	init_state->autoplay(ENHCLICK, NONE);
	init_state->autoplay(ENHCLICK, NONE);

	ll best_cookies = init_state->cookies;
	StatePtr best_state = init_state;

	StatePtr state(new State(*init_state));
	map<int, ll> turns_prods;

	while (state->greedy()) {
		//state->greedy();
		//cerr << state->turn << ": " << state->prod_sum() << endl;
		turns_prods[state->turn] = state->prod_sum();
	}
	//if (state->turn != N) cerr << state->turn << endl;

	ll T = state->turn;
	// 0 ターンまで巻き戻し
	state->rewind(0);
	for (int i = 0; i < T; i++) {
		state->action(EAct(state->hist_act[i]), EBld(state->hist_bld[i]));
		// 5000 ターン以降のキーフレーム
		if (state->turn >= 5000 && turns_prods.find(state->turn) != turns_prods.end()) {
			// 全部クリック
			for (int j = 40; j >= 0; j--) {
				StatePtr s(new State(*state));
				for (int t = s->turn; t < N - j; t++)
					s->action(CLICK, NONE);
				//cerr << "before sell: " << s->cookies << ", ";
				//for (int t = s->turn; t < N; t++) s->sell_highest();
				if (!s->sell_blds(j)) cerr << "error!" << endl;
				//cerr << "after sell: " << s->cookies << endl;
				//cerr << state->turn << ": " << s->cookies << endl;
				if (best_cookies < s->cookies) {
					best_cookies = s->cookies;
					best_state = s;
					//cerr << best_cookies << endl;
				}
			}
		}
	}

	//cerr << loopcnt << endl;

	return best_state;
}

//State BeamSearch(State FirstState) {
//	Heap<State> HNowStates = new Heap<State>();
//	HNowState.push(FirstState) :
//		int k = 100; // ビーム幅
//	for (size_t t = 0; t < MaxTurn; t++) {
//		Heap<State> HNextStates = new Heap<State>();
//		for (size_t i = 0; i < k; i++) {
//			if (HNowStates.top == null) break;
//			var NowState = HNowStates.pop();
//			foreach(var NextState in NowState.GetAllNextState()) {
//				HNextStates.push(NextState);
//			}
//		}
//		HNowStates = HNextStates;
//	}
//	var BestState = HNowStates.pop();
//	return BestState;
//}

typedef pair<double, StatePtr> Obj;
bool operator < (const Obj& a, const Obj& b) {
	return a.first == b.first ? a.second->prod_sum() > b.second->prod_sum() : a.first < b.first;
}

bool operator < (const StatePtr& a, const StatePtr& b) {
	return a->prod_sum() > b->prod_sum();
}

vector<Obj> getAllNextState(const Obj& obj) {
	vector<Obj> res;
	const auto& state = obj.second;
	ll cur_turn = state->turn;
	ll cur_prod_sum = state->prod_sum();

	for (auto act : { BUY, REINFORCE, ENHCLICK }) {
		auto bs = (act == ENHCLICK ? vector<EBld>({ NONE }) : blds);
		for (auto bld : blds) {
			StatePtr next_state(new State(*state));
			if (!next_state->autoplay(act, bld)) continue;
			ll next_turn = next_state->turn;
			ll next_prod_sum = next_state->prod_sum();
			double score = log(1.0 + double(next_prod_sum - cur_prod_sum) / next_prod_sum) / (next_turn - cur_turn);
			res.emplace_back(score, next_state);
		}
	}

	return res;
}

StatePtr beam_search(const StatePtr& init_state) {
	priority_queue<StatePtr> best_states;

	StatePtr state(new State(*init_state));

	priority_queue<Obj> now_states;
	now_states.emplace(0.0, state);
	ll max_prod = 0;
	int width = 1;
	int loopcnt = 0;
	while (!now_states.empty()) {
		priority_queue<Obj> next_states;
		for (int i = 0; i < width; i++) {
			if (now_states.empty()) break;
			//set<double> scores;
			auto now_state = now_states.top(); now_states.pop();
			for (auto next_state : getAllNextState(now_state)) {
				//if (scores.find(next_state.first) != scores.end()) continue;
				//scores.insert(next_state.first);
				next_states.push(next_state);
			}
		}
		now_states = next_states;
		if (now_states.empty()) break;
		//cerr << "loopcnt: " << loopcnt << endl;
		while (!next_states.empty()) {
			auto s = next_states.top(); next_states.pop();
			//cerr << s.second->turn << ": " << s.second->prod_sum() << " " << s.first << endl;
			if (s.second->prod_sum() > max_prod) {
				best_states.push(s.second);
				if (best_states.size() >= 10) best_states.pop();
				max_prod = s.second->prod_sum();
				//cerr << s.second->turn << ": " << max_prod << endl;
			}
		}
		auto top = now_states.top().second;
		//cerr << top->turn << ": " << top->prod_sum() << endl;
		loopcnt++;
	}

	//cerr << best_states.size() << endl;

	StatePtr best_state = solve(init_state);
	ll best_cookies = best_state->cookies;

	while (!best_states.empty()) {
		auto state = best_states.top(); best_states.pop();
		ll max_turn = state->turn;

		set<int> turns_prods;

		for (int i = 0; i < state->turn; i++) {
			if (state->hist_act[i] != CLICK) {
				turns_prods.insert(i);
			}
		}

		// 0 ターンまで巻き戻し
		state->rewind(0);
		for (int i = 0; i < max_turn; i++) {
			state->action(EAct(state->hist_act[i]), EBld(state->hist_bld[i]));
			// 5000 ターン以降のキーフレーム
			if (state->turn >= 5000 && turns_prods.find(state->turn) != turns_prods.end()) {
				// 全部クリック
				for (int i = 40; i >= 0; i--) {
					StatePtr s(new State(*state));
					for (int t = s->turn; t < N - i; t++)
						s->action(CLICK, NONE);
					//cerr << "before sell: " << s->cookies << ", ";
					//for (int t = s->turn; t < N; t++) s->sell_highest();
					if (!s->sell_blds(i)) cerr << "error!" << endl;
					//	if (!s->sell_highest()) cerr << "error!" << endl;
					//cerr << "after sell: " << s->cookies << endl;
					//cerr << state->turn << ": " << s->cookies << endl;
					if (best_cookies < s->cookies) {
						best_cookies = s->cookies;
						//cerr << best_cookies << endl;
						best_state = s;
					}
				}
			}
		}

	}
	return best_state;
}

string testcase(unsigned seed) {
	SXor128 r(seed);
	REP(i, 100) r.nextUInt();

	int range_min = 0, range_max = 199;
	string S(N, 'N');
	while (range_min < N) {
		int idx = r.nextUInt(range_min, range_max);
		if (idx >= N) break;
		int kind = r.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;
//	EBld bld;
//	string text;
//	cv::Mat_<cv::Vec3b> 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_<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, EBld(i), "buy " + dict_blds_inv.at(EBld(i)));
//		buttons.emplace_back(250, 100 * i + 50, 500, 100 * i + 100, REINFORCE, EBld(i), "reinforce " + dict_blds_inv.at(EBld(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;
//		EBld 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;
//			EBld 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;
//			EBld maxbld = NONE;
//			for (int i = 4; i >= 0; i--) {
//				ll d = state->diff(SELL, EBld(i));
//				if (maxsell < d) {
//					maxsell = d;
//					maxbld = EBld(i);
//				}
//			}
//			if (maxsell != -1) {
//				state->action(SELL, maxbld, maxsell);
//			}
//		}
//		else {
//			key = 27;
//		}
//
//	} while (key != 27);
//}
//#endif

#ifdef _MSC_VER
int _main() {
	timer.measure();

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

	int T = 256;
	vector<ll> scores(T);
	vector<unsigned> seeds(T);
	REP(i, 100) rnd.nextUInt();

	REP(i, T) seeds[i] = /*rnd.nextUInt()*/i;

	//for (int i = 0; i < T; i++) {
	concurrency::parallel_for(0, T, [&](int i) {
		ofstream ofs("input_" + to_string(i) + ".txt");

		unsigned seed = seeds[i];

		string S(testcase(seed));
		StatePtr state(new State(S));

		state = solve(state);

		ofs << N << endl << S << endl;

		for (int i = 0; i < state->turn; i++) {
			EAct act = EAct(state->hist_act[i]);
			EBld bld = EBld(state->hist_bld[i]);
			ofs << dict_acts_es.at(act);
			if (act != CLICK && act != ENHCLICK) ofs << " " << dict_blds_es.at(bld);
			ofs << endl;
		}

		cerr << seed << " ";
		scores[i] = state->cookies;
	});
	//}


	REP(i, T) cerr << "seed " << seeds[i] << ": " << scores[i] << endl;

	cerr << endl;
	cerr << "total: " << accumulate(all(scores), 0LL) / (T / 32) << endl;

	return 0;
}
#endif

int main() {
	timer.measure();

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

	int buf;
	string S;
	cin >> buf >> S;
	//string S = testcase(0);

	StatePtr state(new State(S));

	state = solve(state);
	//state = beam_search(state);

	cerr << state->cookies << endl;

	string retval;
	for (int i = 0; i < state->turn; i++) {
		EAct act = EAct(state->hist_act[i]);
		EBld bld = EBld(state->hist_bld[i]);
		cout << dict_acts_es.at(act);
		if (act != CLICK && act != ENHCLICK) cout << " " << dict_blds_es.at(bld);
		cout << endl;
		cin >> retval;
	}

	return 0;
}