#include #include #include // テンプレート引数 // S : オペランドの型 // read_S : 引数の入力ストリームからオペランドを 1 つ読み込んで返す関数のポインタ // op_add : S どうしの足し算を計算する関数のポインタ // op_sub : S どうしの引き算を計算する関数のポインタ // op_mul : S どうしの掛け算を計算する関数のポインタ template< class S, S(*read_S)(std::istream&), S(*op_add)(S, S), S(*op_mul)(S, S), S(*op_paren)(S) > class parse { private: enum Op_Symbol { Op_Symbol_Add, Op_Symbol_Mul, Op_Symbol_BracketOpen }; struct parse_stack { // オペランドの位置関係 std::vector St; // 演算子と括弧の位置関係 // 優先順位が低い順に並ぶので、後ろから計算される std::vector OpSymbols; // OpSymbols の最後の要素を、適切な操作を伴って削除する // Op_Symbol_BracketOpen の場合は取り除かれるだけ void remove_last_op() { switch (OpSymbols.back()) { case Op_Symbol_Add: { S r = St.back(); St.pop_back(); S l = St.back(); St.pop_back(); St.push_back(op_add(l, r)); } break; case Op_Symbol_Mul: { S r = St.back(); St.pop_back(); S l = St.back(); St.pop_back(); St.push_back(op_mul(l, r)); } break; case Op_Symbol_BracketOpen: { } break; } OpSymbols.pop_back(); } }; public: // 引数の入力ストリームから EOF まで式を読み込み、評価する。 // 読み込まれる式が正しくない場合、未定義動作。 S calc(std::istream& istr) const { parse_stack st; while (true) { char c; istr >> c; if (istr.eof()) break; if (c == '(') { // Op_Symbol_BracketOpen は ')' が来たときに取り除かれる st.OpSymbols.push_back(Op_Symbol_BracketOpen); continue; } else if (c == ')') { // 優先順位の高いものをすべて計算 // カッコ内すべて bool pop_done = false; while (!st.OpSymbols.empty() && !pop_done) { switch (st.OpSymbols.back()) { case Op_Symbol_Add: case Op_Symbol_Mul: { st.remove_last_op(); } break; default: { pop_done = true; } } } // Op_Symbol_BracketOpen を取り除く st.St.back() = op_paren(st.St.back()); st.OpSymbols.pop_back(); } else if (c == '$') { // 優先順位の高い掛け算はすべて計算 // 掛け算または左側の足し算引き算 bool pop_done = false; while (!st.OpSymbols.empty() && !pop_done) { switch (st.OpSymbols.back()) { case Op_Symbol_Add: case Op_Symbol_Mul: { st.remove_last_op(); } break; default: { pop_done = true; } } } // 現時点で優先順位最高 st.OpSymbols.push_back(Op_Symbol_Add); } else if (c == '&') { bool pop_done = false; // 優先順位の高いものをすべて計算 // 左側の掛け算 while (!st.OpSymbols.empty() && !pop_done) { switch (st.OpSymbols.back()) { case Op_Symbol_Mul: { st.remove_last_op(); } break; default: { pop_done = true; } } } // 優先順位が現時点で最高なので、OpSymbolsの最後に足すだけでよい st.OpSymbols.push_back(Op_Symbol_Mul); } else { // 演算子や括弧ではないので、オペランドとして読み込む istr.unget(); st.St.push_back(read_S(istr)); } } // 残りを計算 while (!st.OpSymbols.empty()) { st.remove_last_op(); } return st.St.back(); } }; #include #include #include #include #include using namespace std; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; #define rep(i,n) for(int i=0; i<(int)(n); i++) vector opLeft; vector opRight; vector opType; vector expSize; vector expPos; vector expVal; int read_S(istream& cin){ int v; cin >> v; int res = opType.size(); opLeft.push_back(-1); opRight.push_back(-1); opType.push_back(v); expSize.push_back(to_string(v).size()); expVal.push_back(-1); expPos.push_back(0); return res; } int op_add(int l, int r){ int res = opType.size(); opLeft.push_back(l); opRight.push_back(r); opType.push_back(-1); expSize.push_back(expSize[l] + expSize[r] + 1); expVal.push_back(-1); expPos.push_back(0); return res; } int op_mul(int l, int r){ int res = opType.size(); opLeft.push_back(l); opRight.push_back(r); opType.push_back(-2); expSize.push_back(expSize[l] + expSize[r] + 1); expVal.push_back(-1); expPos.push_back(0); return res; } int op_paren(int l){ int res = opType.size(); opLeft.push_back(l); opRight.push_back(-1); opType.push_back(-3); expSize.push_back(expSize[l] + 2); expVal.push_back(-1); expPos.push_back(0); return res; } using Parse = parse; int main(){ int M; cin >> M; int C; cin >> C; Parse().calc(cin); /* rep(i,opType.size()){ cout << "i = " << i << " , "; cout << "l = " << opLeft[i] << " , "; cout << "r = " << opRight[i] << " , "; cout << "ty = " << opType[i] << " , "; cout << endl; } cout << endl; */ vector> dp(opType.size()); bitset<301> mask; rep(i,M+1) mask.set(i); rep(i,opType.size()){ if(opType[i] >= 0){ dp[i].set(opType[i]); } else if(opType[i] == -1){ for(int d=0; d<=M; d++){ if(!dp[opRight[i]].test(d)) continue; dp[i] |= dp[opLeft[i]] << d; dp[i] |= dp[opLeft[i]] >> d; } dp[i] &= mask; } else if(opType[i] == -2){ for(int d=0; d<=M; d++) if(dp[opLeft[i]].test(d)) for(int e=0; d*e<=M && e<=M; e++) if(dp[opRight[i]].test(e)){ dp[i].set(d*e); } vector imos(M+2, 0); rep(d,M+1) imos[d+1] = imos[d] + (dp[opLeft[i]].test(d) ? 1 : 0); for(int d=1; d<=M; d++) if(dp[opRight[i]].test(d)) for(int t=0; d*t<=M && t<=M; t++) if(imos[min(M+1,d*(t+1))] - imos[d*t]){ dp[i].set(t); } } else if(opType[i] == -3){ dp[i] = dp[opLeft[i]]; } } //rep(i,opType.size()) cout << dp[i] << endl; //cout << endl; if(!dp.back().test(C)){ cout << "-1\n"; return 0; } expVal.back() = C; string res(expSize.back(), ' '); for(int i=(int)opType.size()-1; i>=0; i--){ //cout << "i = " << i << " , "; //cout << "val = " << expVal[i] << " , "; //cout << "ty = " << opType[i] << endl; if(!dp[i].test(expVal[i])){ cout << "value error" << endl; return 0;} if(opType[i] >= 0){ string tmp = to_string(opType[i]); copy(tmp.begin(), tmp.end(), res.begin() + expPos[i]); } else if(opType[i] == -1){ expPos[opLeft[i]] = expPos[i]; expPos[opRight[i]] = expPos[i] + expSize[opLeft[i]] + 1; int v = expVal[i]; bool done = false; for(int l=0; l<=v; l++) if(dp[opLeft[i]].test(l) && dp[opRight[i]].test(v-l)){ expVal[opLeft[i]] = l; expVal[opRight[i]] = v-l; res[expPos[i] + expSize[opLeft[i]]] = '+'; done = true; break; } for(int l=v; l<=M; l++) if(dp[opLeft[i]].test(l) && dp[opRight[i]].test(l-v)){ expVal[opLeft[i]] = l; expVal[opRight[i]] = l-v; res[expPos[i] + expSize[opLeft[i]]] = '-'; done = true; break; } if(!done) return 0; } else if(opType[i] == -2){ expPos[opLeft[i]] = expPos[i]; expPos[opRight[i]] = expPos[i] + expSize[opLeft[i]] + 1; int v = expVal[i]; bool done = false; for(int d=0; !done && d<=M; d++) if(dp[opLeft[i]].test(d)) for(int e=0; d*e<=M && e<=M; e++) if(d*e == v) if(dp[opRight[i]].test(e)){ expVal[opLeft[i]] = d; expVal[opRight[i]] = e; res[expPos[i] + expSize[opLeft[i]]] = '*'; done = true; break; } vector imos(M+2, 0); rep(d,M+1) imos[d+1] = imos[d] + (dp[opLeft[i]].test(d) ? 1 : 0); for(int d=1; !done && d<=M; d++) if(dp[opRight[i]].test(d)) if(imos[min(M+1,d*(v+1))] - imos[d*v]){ for(int e=d*v; e<=M; e++) if(dp[opLeft[i]].test(e)){ expVal[opLeft[i]] = e; expVal[opRight[i]] = d; res[expPos[i] + expSize[opLeft[i]]] = '/'; done = true; break; } } if(!done) return 0; } else if(opType[i] == -3){ expPos[opLeft[i]] = expPos[i] + 1; expVal[opLeft[i]] = expVal[i]; res[expPos[i]] = '('; res[expPos[i] + 1 + expSize[opLeft[i]]] = ')'; } //cout << "res = " << res << endl; } cout << res << '\n'; return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } ios_do_not_sync_instance;