問題一覧 > 通常問題

No.2069 Mi-World Expressions

レベル : / AI推定難易度 : 1750 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 12
作問者 : okkuu / テスター : akakimidori Michirakara
お気に入りにしたユーザー ProblemId : 8282 / 自分の提出
問題文最終更新日: 2022-09-09 21:11:37
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Problem Statement

The mathematical expressions used in "Mi-World", where Michirakara lives, seem to be slightly different from the expressions in our world.
Specifically, expressions in Mi-World have the following characteristics.

  • Only the four arithmetic operations and parentheses are used (note that $+$ and $-$ do not appear as unary operators either).
  • The order of evaluation is the same as in our world: the contents of parentheses, then multiplication and division, then addition and subtraction.
  • Among operations of the same priority, evaluation is always performed from the left.
  • Only integers between $0$ and $M$, inclusive, appear during the calculation (this includes the initial values and the final answer).
  • Among the four arithmetic operations, floor division (the operation of dividing and then rounding down) is used instead of division.
  • The symbols for addition and subtraction are extremely similar (here both are denoted by $\$$).
  • The symbols for multiplication and floor division are also extremely similar (here both are denoted by $\&$).
  • As in our world, division by $0$ is not allowed.
Strictly speaking, an expression used in Mi-World is an <expression> in the following BNF (or something like it).
<expression>::=<term>|<expression>'$'<term>
<term>::=<factor>|<term>'&'<factor>
<factor>::=<number>|'('<expression>')'
<number>::=0以上M以下の整数
Michirakara has brought a Mi-World expression to our world.
Convert this expression into an expression of our world.
Specifically, replace each $\$$ with $+$ (addition) or $-$ (subtraction) and each $\&$ with $*$ (multiplication) or $/$ (floor division), and output the result.
If there are multiple ways to convert it, you may output any of them.
However, if there is no way to convert it (the expression itself is wrong), output $-1$.
(Original idea: Michirakara)

Input

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

  • $M$ and $\text{ans}$ are integers
  • $1\leqq M\leqq300$
  • $0\leqq\text{ans}\leqq M$
  • $1\leqq|\text{expr}|\leqq1000$
  • $\text{expr}=\text{ans}$ is valid in form as an expression used in Mi-World (see Sample 4)
  • The input represents the equation $\text{expr}=\text{ans}$ (see the samples for details).
    Addendum: For the exact input constraints, refer to the question section.

Output

Output $\text{expr}$ with each $\$$ and $\&$ replaced as specified in the problem statement.
However, if this is impossible, output $-1$.
Do not forget the newline at the end.

Sample

Sample 1
Input
100 21
1$2&3$4&5
Output
1+2/3+4*5

The input represents the equation $1\$2\&3\$4\&5=21$.
Since $1+2/3+4*5=21$, outputting $1+2/3+4*5$ is correct.
Note that $2/3$ evaluates to $0$.
Outputting $1-2/3+4*5$ is also correct.

Sample 2
Input
100 51
2&51&2
Output
-1

The input represents the equation $2\&51\&2=51$.
Although $2*51/2=51$, note that this is invalid as a Mi-World expression because it exceeds $M=100$ partway through (at the point of $2*51$).

Sample 3
Input
100 0
2&(4$3)
Output
2/(4+3)

Note that the input may contain parentheses.

Sample 4
Input
300 0
150$200
Output
-1

Whether $\$$ means addition or subtraction, $150\$200$ is invalid as a Mi-World expression.
Note that such inputs may also be included.
However, all numbers initially contained in $\text{expr}$ are between $0$ and $M$, inclusive.
(That is, for example, an input where $M$ is $100$ and $\text{expr}$ is $150\$200$ is not included in the test cases.)

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