No.3021 Maximize eval
タグ : / 解いたユーザー数 73
作問者 : 👑


問題文
Python3
,PyPy3
にはeval
という関数が標準ライブラリに存在します。(公式リファレンス)これは、引数の文字列をコードとして解釈し、その結果を返す関数です。例えば、
eval("1+1")
を実行すると、$2$ が返ってきます。
次の条件を満たす文字列 $X$ を計算可能文字列と定義します。
- $X$ の各文字は $0$ を除く数字または演算子(
123456789+-
のいずれか)である - $X$ の末尾の文字は $0$ を除く数字(
123456789
のいずれか)である - $X$ の中で演算子(
+-
のいずれか)同士は隣り合わない
$0$ を除く数字、演算子、?
(123456789+-?
のいずれか)からなる文字列 $S$ が与えられます。
ここで、$S$ に含まれるすべての ?
をそれぞれ $0$ を除く数字または演算子(123456789+-
のいずれか)に置き換えることで、計算可能文字列 $S'$ を作ることを考えます。
このように生成できる計算可能文字列 $S'$ のうち、数式として解釈したときの計算結果が最大となるものを求めてください。ただし、本問題の制約下において必ず $S'$ を生成できることが保証されます。
$T$ 個のテストケースが与えられるので、それぞれについて答えてください。
制約
- $1 \leq T \leq 10^4$( $T$ は整数である)
- $1 \leq |S| \leq 5 \times 10^5$( $|S|$ は $S$ の長さである)
- 各入力について、すべてのテストケースにおける $|S|$ の総和は $5 \times 10^5$ 以下である
- $S$ の各文字は
123456789+-?
のいずれかである - $S$ の末尾の文字は $0$ を除く数字(
123456789
のいずれか)または?
である - $S$ の中で演算子(
+-
のいずれか)同士は隣り合わない
入力
入力は以下の形式で標準入力から与えられます。ここで、$\mathrm{case}_i ~ (i = 1, 2, \cdots, T)$ は $i$ 個目のテストケースです。
$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$
各テストケースは以下の形式で与えられます。
$S$
出力
$T$ 行出力し、 $i$ 行目には $i$ 個目のテストケースについての答えを出力してください。
各テストケースについて、生成できる $S'$ のうち、数式として解釈したときの計算結果が最大となるものを出力してください。
サンプル
サンプル
入力
5 2?-?? -??? ?-???-? 3-141+592-653-589+793 ????????????????????????????????????????????????????????????????????????????????
出力
29-11 -1+9 9-1+9-1 3-141+592-653-589+793 99999999999999999999999999999999999999999999999999999999999999999999999999999999
各テストケースについて、以下のことが言えます。
- $1$ 個目のテストケースについて、この $S'$ を数式と解釈したときの計算結果は $29 - 11 = 18$ です。
- $5$ 個目のテストケースについて、与えられる $S$ 次第では計算結果が非常に大きくなる場合もあります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。