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