No.10 +か×か

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / タグ : / 解いたユーザー数 111
作問者 : yuki2006yuki2006

1 ProblemId : 29 / 出題時の順位表

問題文

あなたは、Isaacから借りたノートをコピーしようとしてOCRにかけようとしている。
ある計算式をOCRしようとしたら、演算子を正しく認識されてなく、文字化けしていることに気づいた。
ここに出てくる演算子は+と*のみで、すべて?と表示されてしまっている。
元の数式の正しい数式を求めてください。
複数回答がある場合は、{+,*} の順の辞書列順の最初のものを求めてください。
例えば辞書順は
++ \(\rightarrow\) +* \(\rightarrow\) *+ \(\rightarrow\) ** の順番である。

重要:この問題では優先順位は同じとし、左結合とする。
簡単に言うと左から順に処理するだけである。
例えば1 ? 2 ? 10 ? 1=31の場合 1+2*10+1が答えで
実際の世界では((1+2)*10)+1=31 となるので注意。

入力

\(N\)
\(Total\)
\(A_1\ A_2\ \dots\ A_N\)

\(1\)行目に、計算式中の整数の数を表す\(N\ (2 \leq N \leq 50) \)が与えられる。
\(2\)行目に、計算式の演算結果を表す\( Total\ (1 \leq Total \leq 100,000) \)が与えられる。
\(3\)行目に 計算式中の整数を表す\( A_i\ (1 \leq A_i \leq 10) \) がスペース区切りで\(N\)個与えられる。

少なくともひとつは、
A1 ? A2 ? A3 ?....? AN = Totalを満たす解があるものとする。

出力

それぞれの演算子を順番に並べたものを出力してください。
(空白などの区切り文字はつけない)
最後に改行してください。

サンプル

サンプル1
入力
4
31
1 2 10 1
出力
+*+

サンプル2
入力
3
6
2 3 1
出力
++

**でも成り立つが、{+*}の辞書列順の最初なので++となる。

サンプル3
入力
3
2
1 1 2
出力
**

提出ページヘ