No.2784 繰り上がりなし十進和
タグ : / 解いたユーザー数 53
作問者 : 👑
p-adic
/ テスター :
hamamu
問題文
数字 から のみからなる長さ の文字列を 桁の数字と呼びます。
入力に 個の 桁の数字 が与えられます。
最初に集合 が として与えられています。
以下の操作を好きなだけ繰り返すことで を更新した時の の要素数の最大値を求めてください。
- の要素 と （同じでも良い）を好きに選び、 と の繰り上がりなし十進和を に追加する。
ここで 桁の数字 と の繰り上がりなし十進和とは、以下を満たす唯一の 桁の数字 のことです。
- 以下の任意の正整数 に対し、次の 数が等しい。
- の左から 文字目の表す数と の左から 文字目の表す数の和を で割った余り。
- の左から 文字目の表す数。
入力
入力は以下の形式で標準入力から 行で与えられます：
- 以下の任意の正整数 に対し、 行目に が与えられます。
制約
入力は以下の制約を満たします：
- 以下の任意の正整数 に対し、 は 桁の数字である。
出力
問題文に指定された操作を好きなだけ繰り返すことで を更新した時にありえる の要素数の最大値を 行に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
000000 000000 000000 000000 000000 000002
このように入力のいくつかが一致することもあります。
出力
5
最初 が として与えられています。
まず の要素 と をともに として選び と の繰り上がりなし十進和 を に追加すると、 は となります。
次に の要素 と をそれぞれ と として選び と の繰り上がりなし十進和 を に追加すると、 は となります。
更に の要素 と をそれぞれ と として選び と の繰り上がりなし十進和 を に追加すると、 は となります。
この時の の要素数は です。元の をどのように操作しても要素数を より大きくすることはできません。
サンプル2
入力
500000 050000 005000 000500 000050 000005
出力
64
に操作を繰り返すことで、各桁が か である 桁の数字を全て に追加することが可能です。例えば は と の繰り上がりなし十進和として得られますし、 は と の繰り上がりなし十進和として得られます。
逆に に操作を繰り返して追加できる要素はそのような 桁の数字に限られます。従ってありえる の要素数の最大値は各桁が か である 桁の数字の総数 です。
サンプル3
入力
100000 010000 001000 000100 000010 000001
出力
1000000
に操作を繰り返すことで、 に 桁の数字を全て追加することが可能です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。