E - Formula
問題文
ストーリー
Monoxerが扱える問題の形式はいくつかありますが、そのうちのひとつに数式があります。
専用のキーボードの他に、手書きによる入力をサポートしています。
https://tech.monoxer.com/entry/2022/10/18/170917
畔柳君は、1桁の整数 $N$ 個からなる数列 $A$ を持っています。次の一連の操作を繰り返すことで、持っている数列を $0$ ひとつだけからなる数列にできるでしょうか？できる場合、操作の最小回数も求めてください。
- 数列の要素を好きな順に並び替える
- 数列の要素数を $X$ として、$1$ 以上 $X$ 未満の整数 $i$ を選ぶ。「$A_1 A_2 \ldots A_{i-1} A_i \times A_{i+1} A_{i+2} \ldots A_X$」を、十進法で$i$桁の数と$X-i$桁の数の掛け算とみて計算し、その積を$P$とする
- $P$ を十進法で書き表したとき、$P$ の桁数を $Y$ とおく。$P$ の上から $j$ 桁目を $P_j$ と表すとき、$A$ を $P_1, P_2, \ldots, P_Y$ で置き換える
制約
- $2 \le N \le 4$
- $0 \le A_i \le 9$
入力
$A_1$ $A_2$ $\ldots$ $A_N$
出力
持っている数列を $0$ ひとつだけからなる数列にできる場合は、操作回数の最小値を 1 行に出力してください。できない場合は $-1$ を出力してください。
3
1 5 7
2
-
1 5 7 を並べ替えて 7 1 5 にする。
-
$X = 3$ である。 $i = 1$ とすると $A_1 A_2 \ldots A_{i-1} A_i = 7$ であり、 $A_{i+1} A_{i+2} \ldots A_X = 15$ である。これらの積は $P = 105$ である。
-
$P$ の桁数は $Y = 3$ である。 $A$ は長さ 3 の数列 1 0 5 になる。
-
1 0 5 を並べ替えて 0 1 5 にする。
-
$X = 3$ である。 $i = 1$ とすると $A_1 A_2 \ldots A_{i-1} A_i = 0$ であり、 $A_{i+1} A_{i+2} \ldots A_X = 15$ である。これらの積は $P = 0$ である。
-
$P$ の桁数は $Y = 1$ である。 $A$ は長さ 1 の数列 0 になる。
以上が操作 $2$ 回で持っている数列を $0$ ひとつだけからなる数列にする方法の例です。操作 $1$ 回以下で持っている数列を $0$ ひとつだけからなる数列にすることはできないので、答えは $2$ です。
2
4 3
-1
4
9 9 9 9
2
4
0 0 0 0
1
- のステップで、 0 0 0 0 を 0 と 0 0 0 に分割すると後者は十進数として解釈した場合に先頭に余分な 0 がありますが、これは問題ないことに注意してください。