// #pragma GCC optimize ("-Ofast") #ifdef LOCAL_TEST #define _GLIBCXX_DEBUG #endif #include #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(cmd == Command::CLICK){ return command_name[(int)cmd]; }else 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){ return (p * 6 + 4) / 5; } void init_buy_price(){ for(int i=1; i (1ll<<40)) break; } } } Int next_enh_price(Int p){ return p * 10; } void init_enh_price(){ for(int i=0; i (1ll<<40)) break; } } } Int next_prod(Int p){ return p * 2; } void init_prod(){ for(int i=0; i (1ll<<40)) break; } } } array level_hash{}; array cnt_hash{}; void init_hash(){ for(int i=0; i, 10005> table{}; struct state{ Int click; Int prod_per_turn; Int pay; array level{}; array cnt{}; }; array st{}; struct beam_state{ // Int cookie; vector phase_cookie; vector v; int64_t hash; array level{}; array cnt{}; }; int n; string S; array fever{}; class Solver{ public: Solver(istream& is){ is >> n; is >> S; init(); } void init(){ S = "N" + S; for(int i=1; i(fever[i-1] - 1, fever[i]); } init_facilities(); } void solve(){ beam_search(); } int turn_step = 25; vector get_phase_cookie(){ vector res; for(int s=turn_step; s<=n; s+=turn_step){ res.emplace_back(table[s][0].cookie); } return res; } void beam_search(){ constexpr int bw = 2; array, 2> beam; vector basic = { (int)Command::REINFORCE * 8 + (int)Facility::CLICK, }; array cnt__{}; array lev__{}; for(int f=0; f& command){ st[0] = state{ 1, 0, 0, {0, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0} }; for(int i=0; i> 3; int f = command[i] & 7; if(c == (int)Command::BUY){ st_.prod_per_turn += prod[f][st_.level[f]]; st_.pay = buy_price[f][st_.cnt[f]]; st_.cnt[f]++; }else if(c == (int)Command::REINFORCE){ Int diff = prod[f][st_.level[f] + 1] - prod[f][st_.level[f]]; if(f == (int)Facility::CLICK){ st_.click += diff; }else{ st_.prod_per_turn += diff * st_.cnt[f]; } st_.pay = enh_price[f][st_.level[f]]; st_.level[f]++; } } table[0][0] = dp_state{ 0, -1, -1, 0 }; int last_size = 1; for(int i=0; i& command){ int back = 70; state last = st[command.size()]; pair> best = pair>{table[n-back][0].cookie, {}}; vector ord = {(int)Facility::FACTORY ,(int)Facility::CASINO, (int)Facility::GRIMOIRE}; sort(ord.begin(), ord.end(), [&](int a, int b){ return prod[a][last.level[a]] < prod[b][last.level[b]]; }); map, pair>> sell_dp; vector initial_vec = vector{ last.cnt[ord[0]], last.cnt[ord[1]], last.cnt[ord[2]]}; sell_dp[initial_vec] = pair>{table[n-back][0].cookie, {}}; for(int i=n-back; i, pair>> sell_dp_; for(auto cur: sell_dp){ if(cur.first == initial_vec){ // click Int gain = last.click + last.prod_per_turn; for(int j=0; j next_state = cur.first; vector next_v = cur.second.second; next_v.push_back((int)Command::CLICK * 8); if(sell_dp_.count(next_state) == 0 || sell_dp_[next_state].first < next_cookie){ sell_dp_[next_state] = pair>{next_cookie, next_v}; } } for(int j=0; j<3; j++){ if(cur.first[j] && (j == ord.size()-1 || cur.first[j+1] == last.cnt[ord[j+1]]) ){ Int next_cookie = cur.second.first + (buy_price[ord[j]][cur.first[j] - 1] * 25 + 99) / 100; Int gain = last.click + last.prod_per_turn; for(int jj=0; jj next_state = cur.first; next_state[j]--; vector next_v = cur.second.second; next_v.push_back((int)Command::SELL * 8 + ord[j]); if(sell_dp_.count(next_state) == 0 || sell_dp_[next_state].first < next_cookie){ sell_dp_[next_state] = pair>{next_cookie, next_v}; } } } } swap(sell_dp, sell_dp_); } for(auto cur: sell_dp){ if(best.first < cur.second.first){ best = cur.second; } } eprintln("score after selling = ", best.first * 1e-9); // restore(command); // restore(best.second); auto res = restore_from_dp(); for(int i=0; i>3), (Facility)(m&7)); } output(res); return best.first; } vector> restore_from_dp(){ vector> res; int i = n; int j = 0; while(i){ auto& st = table[i][j]; int i_ = i-1; int j_ = st.prev_idx; res.emplace_back((Command)(st.last_command >> 3), (Facility)(st.last_command & 7)); i = i_; j = j_; } reverse(res.begin(), res.end()); return res; } vector restore(const vector& command){ for(int i=0; i> 3; int f = command[i] & 7; eprintln(command_name[c], facility_name[f]); } return {}; } void output(vector>& res){ assert(res.size() == n); string tmp; for(int i=0; i> tmp; assert(tmp == "ok"s); } } }; int main(int argc, char* argv[]){ timer::init(); for(int i=1; i+1