問題一覧 > 通常問題

No.2069 み世界数式

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 9
作問者 : okkuukenkenokkuukenken / テスター : MichirakaraMichirakara akakimidoriakakimidori
0 ProblemId : 8282 / 自分の提出
問題文最終更新日: 2022-09-09 21:11:37

問題文

Michirakara君のいる「み世界」で使われている数式は、私達の世界の数式とは少し違っているようです。
具体的には、み世界の数式には以下のような特徴があります。

  • 四則演算とカッコしか使われていない(単項演算子としての$+$や$-$も出て来ない事に注意してください)。
  • 計算の優先順位は私達の世界と同じくカッコの中身→乗除算→加減算の順である。
  • 同じ優先順位の中では必ず左から計算する。
  • 計算の過程(これは最初の値や最後の答えも含む)では$0$以上$M$以下の整数しか出て来ない。
  • 四則演算には除算の代わりに切り捨て除算(除算した後に切り捨てる操作)が使われている。
  • 加算と減算の記号が極度に似ている(ここではどちらも$\$$で表す)。
  • 乗算と切り捨て除算の記号も極度に似ている(ここではどちらも$\&$で表す)。
  • 私達の世界と同じく$0$で割る事は出来ない。
厳密な言い方をするなら、み世界で使われている数式は以下のようなBNF(もどき)における<expression>になります。
<expression>::=<term>|<expression>'$'<term>
<term>::=<factor>|<term>'&'<factor>
<factor>::=<number>|'('<expression>')'
<number>::=0以上M以下の整数
Michirakara君はみ世界の数式を私達の世界に持って来ました。
この数式を私達の世界の数式に直してください。
具体的に言うなら、$\$$は$+$(加算)か$-$(減算)に、$\&$は$*$(乗算)か$/$(切り捨て除算)に直して出力してください。
複数通りの直し方があるのならどれを出力しても構いません。
ただし、1通りも直し方がない(そもそもの数式が間違っている)場合は$-1$と出力してください。
(原案:Michirakara)

入力

$M\ \text{ans}$
$\text{expr}$

  • $M$と$\text{ans}$は整数
  • $1\leqq M\leqq300$
  • $0\leqq\text{ans}\leqq M$
  • $1\leqq|\text{expr}|\leqq1000$
  • $\text{expr}=\text{ans}$はみ世界で使われる数式の形式として正しい(サンプル4を参照)
  • 入力は$\text{expr}=\text{ans}$という式を表しています(詳しくはサンプルを参照)。
    追記:厳密な入力の制約は質問欄を参照してください。

出力

$\text{expr}$の$\$$と$\&$を問題文で指定された通りに置き換えて出力してください。
ただし、それが不可能な場合は$-1$と出力してください。
最後に改行するのを忘れないでください。

サンプル

サンプル1
入力
100 21
1$2&3$4&5
出力
1+2/3+4*5

入力は数式$1\$2\&3\$4\&5=21$を表しています。
$1+2/3+4*5=21$なので、$1+2/3+4*5$と出力すると正解になります。
$2/3$が$0$になる事に注意してください。
また、$1-2/3+4*5$と出力しても正解になります。

サンプル2
入力
100 51
2&51&2
出力
-1

入力は数式$2\&51\&2=51$を表しています。
$2*51/2=51$ですが、これは途中($2*51$の時点)で$M=100$を超えるのでみ世界の数式として不適格な事に注意してください。

サンプル3
入力
100 0
2&(4$3)
出力
2/(4+3)

入力にはカッコが含まれ得る事に注意してください。

サンプル4
入力
300 0
150$200
出力
-1

$\$$が加算の意味でも減算の意味でも$150\$200$はみ世界の数式として不適格です。
このような入力も含まれ得る事に注意してください。
ただし、$\text{expr}$に最初から含まれる数は全て$0$以上$M$以下です。
(つまり、例えば$M$が$100$で$\text{expr}$が$150\$200$であるような入力はテストケースに含まれない)

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