問題一覧 > 通常問題

No.10 +か×か

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 244
作問者 : yuki2006
4 ProblemId : 29 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:47:40

問題文

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

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

入力

N
Total
A1 A2  AN

1行目に、計算式中の整数の数を表すN (2N50)が与えられる。
2行目に、計算式の演算結果を表すTotal (1Total100,000)が与えられる。
3行目に 計算式中の整数を表すAi (1Ai10) がスペース区切りで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
出力
**

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。