問題一覧 > 通常問題

No.3021 Maximize eval

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 73
作問者 : 👑 loop0919 / テスター : Iroha_3856 nikoro256
2 ProblemId : 11924 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-02-14 08:16:23

問題文

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もしくは右上の雲マークをクリックしてアカウントを作成してください。