#pragma GCC optimize ("-Ofast") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; namespace { using Integer = long long; //__int128; template istream& operator >> (istream& is, pair& p){return is >> p.first >> p.second;} template istream& operator >> (istream& is, vector& vec){for(T& val: vec) is >> val; return is;} template istream& operator , (istream& is, T& val){ return is >> val;} template ostream& operator << (ostream& os, const pair& p){return os << p.first << " " << p.second;} template ostream& operator << (ostream& os, const vector& vec){for(size_t i=0; i ostream& operator , (ostream& os, const T& val){ return os << " " << val;} template void print(const H& head){ cout << head; } template void print(const H& head, const T& ... tail){ cout << head << " "; print(tail...); } template void println(const T& ... values){ print(values...); cout << endl; } template void eprint(const H& head){ cerr << head; } template void eprint(const H& head, const T& ... tail){ cerr << head << " "; eprint(tail...); } template void eprintln(const T& ... values){ eprint(values...); cerr << endl; } class range{ Integer start_, end_, step_; public: struct range_iterator{ Integer val, step_; range_iterator(Integer v, Integer step) : val(v), step_(step) {} Integer operator * (){return val;} void operator ++ (){val += step_;} bool operator != (range_iterator& x){return step_ > 0 ? val < x.val : val > x.val;} }; range(Integer len) : start_(0), end_(len), step_(1) {} range(Integer start, Integer end) : start_(start), end_(end), step_(1) {} range(Integer start, Integer end, Integer step) : start_(start), end_(end), step_(step) {} range_iterator begin(){ return range_iterator(start_, step_); } range_iterator end(){ return range_iterator( end_, step_); } }; inline string operator "" _s (const char* str, size_t size){ return move(string(str)); } constexpr Integer my_pow(Integer x, Integer k, Integer z=1){return k==0 ? z : k==1 ? z*x : (k&1) ? my_pow(x*x,k>>1,z*x) : my_pow(x*x,k>>1,z);} constexpr Integer my_pow_mod(Integer x, Integer k, Integer M, Integer z=1){return k==0 ? z%M : k==1 ? z*x%M : (k&1) ? my_pow_mod(x*x%M,k>>1,M,z*x%M) : my_pow_mod(x*x%M,k>>1,M,z);} constexpr unsigned long long operator "" _ten (unsigned long long value){ return my_pow(10,value); } inline int k_bit(Integer x, int k){return (x>>k)&1;} //0-indexed mt19937 mt(chrono::duration_cast(chrono::steady_clock::now().time_since_epoch()).count()); template string join(const vector& v, const string& sep){ stringstream ss; for(size_t i=0; i0) ss << sep; ss << v[i]; } return ss.str(); } inline string operator * (string s, int k){ string ret; while(k){ if(k&1) ret += s; s += s; k >>= 1; } return ret; } } namespace timer{ using namespace chrono; steady_clock::time_point start_time; unsigned long long begin_time; unsigned long long int get_cycle() { unsigned int low, high; __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high)); return ((unsigned long long int)low) | ((unsigned long long int)high << 32); } void init(){ start_time = steady_clock::now(); begin_time = get_cycle(); } double sec_per_cycle(){ auto end_time = steady_clock::now(); double elapsed = duration_cast(end_time - start_time).count() * 1e-9; return elapsed / (get_cycle() - begin_time); } // [sec] double get() { static double spc = sec_per_cycle(); return (double)(get_cycle() - begin_time) * spc; } }; class XorShift{ public: uint32_t x; uint32_t y; uint32_t z; uint32_t w; XorShift(){ x = 123456789; y = 362436069; z = 521288629; w = 88675123; } XorShift(uint32_t seed){ x = 123456789; y = 362436069; z = 521288629; w = seed; for(int i=0; i<100; i++){ next(); } } uint32_t next() { uint32_t t = x ^ (x << 11); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } uint32_t operator () () { return next(); } // [0, range) int operator () (int range){ return (((long long)next()) * range) >> 32 ; } // [0, 1.0] double prob(){ return (next()&0xfffffff) * 3.7252903123397e-9; // 0xfffffff = 268,435,455 = 2^28-1 } template T& operator()(vector& v){ return v[ next()%v.size() ]; } template void shuffle(vector& v){ int n = v.size(); for(int i=0; i facility_name{ "click"s, "hand"s, "lily"s, "factory"s, "casino"s, "grimoire"s }; array command_name{ "click"s, "buy"s, "sell"s, "reinforce"s, "enhclick"s, "nothing"s }; string get_command_str(Command cmd, Facility target){ if(target == Facility::NONE){ return command_name[(int)cmd]; }else{ if(target == Facility::CLICK) return command_name[(int)Command::ENHCLICK]; return command_name[(int)cmd] + " " + facility_name[(int)target]; } } array, num_facilities> buy_price{ vector{-1}, vector{150}, vector{2000}, vector{30000}, vector{600000}, vector{10000000} }; array, num_facilities> enh_price{ vector{15}, vector{1500}, vector{20000}, vector{300000}, vector{6000000}, vector{100000000} }; array, num_facilities> prod{ vector{1}, vector{1}, vector{10}, vector{120}, vector{2000}, vector{25000} }; Int next_buy_price(Int p){ // Int hoge = (p * 6 + 4) / 5; // Int res = ceil(p*6.0 / 5.0); // assert(res == hoge); // return res; return (p * 6 + 4) / 5; // return p * 12 / 10 + !!(p * 12 % 10); } Int get_buy_price(Facility f, int cnt){ if((int)buy_price[(int)f].size() <= cnt){ buy_price[(int)f].emplace_back(next_buy_price(buy_price[(int)f].back())); } return buy_price[(int)f][cnt]; } Int next_enh_price(Int p){ return p * 10; } Int get_enh_price(Facility f, int level){ if((int)enh_price[(int)f].size() <= level){ enh_price[(int)f].emplace_back(next_enh_price(enh_price[(int)f].back())); } return enh_price[(int)f][level]; } Int next_prod(Int p){ return p * 2; } Int get_prod(Facility f, int level){ if((int)prod[(int)f].size() <= level){ prod[(int)f].emplace_back(next_prod(prod[(int)f].back())); } return prod[(int)f][level]; } struct Movement{ int turn; Command cmd; Facility target; // shared_ptr prev; int prev; }; struct State{ Int cookie = 0; Int cookie_prod_per_turn = 0; Int future_cookies = 0; array facility_cnt{}; array facility_level{}; // shared_ptr movement; int movement = -1; long long hash = 0; }; constexpr int beam_width = 800; // constexpr int beam_width = 100; constexpr int num_next_state = 5*3 + 3; constexpr int same_state_limt = 1; template struct my_pool{ array pool; array idx; int size = 0; my_pool(){ iota(idx.begin(), idx.end(), 0); } int get(){ return idx[size++]; } void erase(int i){ idx[--size] = i; } int set(const T& v){ int i = get(); pool[i] = v; return i; } }; array, 3> beam_pool{}; array zhash_facility_cnt{}; array zhash_facility_level{}; int main(){ timer::init(); int n; cin >> n; string s; cin >> s; // init my_pool<10005 * beam_width + beam_width * num_next_state, Movement> movement_pool; s = "N" + s; vector fever(s.size(), 0); for(int i=0; i<(int)s.size(); i++){ if(s[i] == 'F'){ fever[i] = 20; } if(i) fever[i] = max(fever[i], fever[i-1]-1); } for(int& i: fever){ i = min(i, 1); } vector fever_acc = fever; for(int i=1; i<(int)fever_acc.size(); i++){ fever_acc[i] += fever_acc[i-1]; } vector next_bonus(s.size(), 0); for(int i=1; i<(int)s.size(); i++){ if(s[i] == 'B'){ next_bonus[i-1] = 1; // next_bonus[i] = 1; } } for(int i=s.size()-2; i>=0; i--){ next_bonus[i] += next_bonus[i+1]; } for(int i=0; i> gain_coeff(num_check_point, vector(s.size(), 0.0)); for(int w=0; w=0; i--){ gain_coeff[w][i] = pow(1.01, next_bonus[i] - next_bonus[j]) * (fever[i]*6 + 1); gain_coeff[w][i] += gain_coeff[w][i + 1]; } } auto calc_future_cookies = [&](State& state, int turn){ turn++; static int check_point = 0; static int j = 0; static int i = -1; static double pk = 1; if(i != turn){ i = turn; check_point = max(0, num_check_point-2 - turn / check_point_interval); j = s.size() - 1 - s.size() * check_point / check_point_interval; pk = pow(1.01, next_bonus[turn] - next_bonus[j]); } Int res = ceil( state.cookie * pk + gain_coeff[check_point][turn] * (state.cookie_prod_per_turn + get_prod(Facility::CLICK, state.facility_level[(int)Facility::CLICK])) ); // Int res = 0; // Int k = 1; // for(int c=0; c prev_beam_ids {0}; beam_pool[0][0] = State{ }; beam_pool[0][0].facility_cnt[0] = 1; beam_pool[0][0].cookie = 0; beam_pool[0][0].cookie_prod_per_turn = 0; beam_pool[0][0].future_cookies = 0; beam_pool[0][0].hash = 0; for(int i=0; i