結果
問題 | No.5003 物理好きクリッカー |
ユーザー |
|
提出日時 | 2018-12-03 17:25:24 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 20,638 bytes |
コンパイル時間 | 2,720 ms |
実行使用メモリ | 36,620 KB |
スコア | 163,422,651,139 |
平均クエリ数 | 10000.00 |
最終ジャッジ日時 | 2021-07-19 08:01:27 |
合計ジャッジ時間 | 6,738 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 WA * 9 |
コンパイルメッセージ
main.cpp: In function ‘void optimal(const StatePtr&)’: main.cpp:183:29: warning: ‘best_bld’ may be used uninitialized in this function [-Wmaybe-uninitialized] losts = cost_purchase[bld]; ~~~~~~~~~~~~~~~~~^ main.cpp:336:10: 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>#endifusing 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 tupletemplate<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 falsestruct 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_VERdouble limit = 9.9;#elsedouble limit = 9.9;#endifdouble 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_VERreturn __rdtsc() / 2.6e9;#elseunsigned long long a, d;__asm__ volatile ("rdtsc" : "=a" (a), "=d" (d));return (d << 32 | a) / 2.8e9;#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);}// actionvoid 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') // Bonustotal_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) {//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);ll cur_turn = state->turn;ll cur_productivity = 0;REP(i, 5) cur_productivity += state->blds_count[i] * state->productivity[i];//while (true) {// 効率のいい ( 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 > 500) 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 > 500) 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);//}}void solve(const StatePtr& state) {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);while (state->turn < N) {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 < 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);}}}}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_VERtypedef 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);}#endifint main() {cin.tie(0);ios::sync_with_stdio(false);//cerr << testcase(0) << endl;int buf;cin >> buf >> S;//S = testcase(0);StatePtr state(new State);solve(state);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;}//while (init_state->turn < N) {// init_state->command();//}//StatePtr final_state = beam_search(init_state);return 0;}