No.2734 Addition and Multiplication in yukicoder (Hard)

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 76
作問者 : 👑

AngrySadEight / テスター :

kusirakusira

FplusFplusF

hiro1729

🦠みどりむし

0 ProblemId : 10762 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2024-04-14 20:12:28

この問題は、問題 B「Addition and Multiplication in yukicoder (Easy)」と似た設定です。問題文の相違点を赤字で示します。

$N$ 個の整数 $A_1, A_2, \dots, A_N$ があります。また、変数 $x$ があり、最初 $x = 0$ です。

あなたは、次に示す操作を $1$ 回行います。

まず、 $(1, 2, \dots, N)$ の順列 $(P_1, P_2, \dots, P_N)$ をひとつ選ぶ。
次に、 $i = 1, 2, \dots, N$ の順に、 $x$ を $10^{d(A_{P_i})} \times x + A_{P_i}$ で置き換える。ただし、 $d(y)$ で $y$ の $10$ 進表記における桁数を表す。

このとき、最終的な $x$ の値として考えられる最小値を $998244353$ で割った余りを求めてください。なお、 $x$ の値を $998244353$ で割った余りの最小値を求めるのではないことに注意してください。

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $A_1$   $A_2$   $\dots$   $A_N$

最終的な $x$ の値として考えられる最小値を $998244353$ で割った余りを出力せよ。

3
23 456 1

$(P_1, P_2, P_3) = (3, 1, 2)$ とすればよいです。このとき、操作の過程での $x$ の値は以下のようになります。

最初、 $x = 0$ である。 $P_1 = 3$ より、 $A_{P_1} = A_3 = 1$ である。 $d(1) = 1$ より、 $x$ を $10^1 \times 0 + 1 = 1$ に置き換える。
$P_2 = 1$ より、 $A_{P_2} = A_1 = 23$ である。 $d(23) = 2$ より、 $x$ を $10^2 \times 1 + 23 = 123$ に置き換える。
$P_3 = 2$ より、 $A_{P_3} = A_2 = 456$ である。 $d(456) = 3$ より、 $x$ を $10^3 \times 123 + 456 = 123456$ に置き換える。

よって、最終的な $x$ の値は $123456$ となり、これが実現可能な最小値です。

5
31 41 5 9 2

9
1 22 333 4444 55555 666666 7777777 88888888 999999999

808067813

$998244353$ で割った余りを出力してください。

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