#include typedef long long ll; typedef unsigned long long ull; #define FOR(i,a,b) for(int (i)=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define RANGE(vec) (vec).begin(),(vec).end() using namespace std; class AddOrMul { public: void solve(void) { int N, Total; cin>>N>>Total; vector A(N); REP(i, N) cin>>A[i]; // 逆方向からパスを作る(順方向でやってハマった) // dp[i][s] = i 番目まで見たときに s の値を作成できるか vector> dp(Total+1, vector(N+1, false)); dp[Total][N] = true; // start mark // O(Total*N) <= 50*10^5 = 5*10^6 for (int i = N-1; i >= 0; --i) REP(s, Total+1) { if (!dp[s][i+1]) continue; if (s-A[i] >= 0) dp[s-A[i]][i] = true; if (s%A[i] == 0) dp[s/A[i]][i] = true; } // 順方向でパスを作成する。 // 作成できないパスは途中でとまっているはず // N // +++++++ <- stop // +++++**+++++ <- stop // +...+++++*++++**+++++ <- reach // +...+**+++*+++++*++++ <- reach // string ans; int s = A[0]; FOR(i, 1, N) { if (s+A[i] <= Total && dp[s+A[i]][i+1]) { ans += "+"; s += A[i]; } else { ans += "*"; s *= A[i]; } } cout<solve(); delete obj; return 0; } #endif