#include "bits/stdc++.h" using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const int INF = 1e9; const ll LINF = 1e18; template ostream& operator << (ostream& out,const pair& o){ out << "(" << o.first << "," << o.second << ")"; return out; } template ostream& operator << (ostream& out,const vector V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; } template ostream& operator << (ostream& out,const vector > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; } template ostream& operator << (ostream& out,const map mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; } /* 問題文============================================================ あなたは、Isaacから借りたノートをコピーしようとしてOCRにかけようとしている。 ある計算式をOCRしようとしたら、演算子を正しく認識されてなく、文字化けしていることに気づいた。 ここに出てくる演算子は+と*のみで、すべて?と表示されてしまっている。 元の数式の正しい数式を求めてください。 複数回答がある場合は、{+,*} の順の辞書列順の最初のものを求めてください。 例えば辞書順は ++ → +* → *+ → ** の順番である。 重要:この問題では優先順位は同じとし、左結合とする。 簡単に言うと左から順に処理するだけである。 例えば1 ? 2 ? 10 ? 1=31の場合 1+2*10+1が答えで 実際の世界では((1+2)*10)+1=31 となるので注意。 ================================================================= 解説============================================================= ================================================================ */ string ans; void rec(int n,int T,string s,vector>& dp,vector& A){ if(n == 0){ reverse(s.begin(),s.end()); ans = max(ans,s); return; } if(dp[n][T-A[n]]) rec(n-1,T-A[n],s+"+",dp,A); if(T%A[n] == 0 && dp[n][T/A[n]]) rec(n-1,T/A[n],s+"*",dp,A); } void solve(){ int N; cin >> N; int T; cin >> T; vector A(N); for(auto& in:A) cin >> in; vector> dp(N+1,vector(T+1,0)); ans = string(N-1,'*'); dp[1][A[0]] = 1; for(int i = 1; i < N;i++){ for(int j = 0; j < T; j++){ if(dp[i][j] == 0) continue; if(j + A[i] <= T) dp[i+1][j+A[i]] = 1; if(j*A[i] <= T) dp[i+1][j*A[i]] = 1; } } rec(N-1,T,"",dp,A); // int now = T; // for(int i = N-1; i > 0; i--){ // if(dp[i][now - A[i]]){ // now = now - A[i]; // ans += "+"; // }else{ // now = now/A[i]; // ans += "*"; // } // } // reverse(ans.begin(),ans.end()); cout << ans << endl; } int main(void) { cin.tie(0); ios::sync_with_stdio(false); solve(); return 0; }