No.2784 Carry-less Decimal Sum
Problem Statement
A string of length $6$ consisting only of the digits $0$ to $9$ is called a $6$-digit number.
The input gives $6$ $6$-digit numbers $A_1, A_2, A_3, A_4, A_5, A_6$.
Initially, a set $S$ is given as $\{A_1, A_2, A_3, A_4, A_5, A_6\}$.
Find the maximum number of elements of $S$ when $S$ is updated by repeating the following operation any number of times.
- Freely choose elements $a$ and $b$ of $S$ (they may be the same), and add the carry-less decimal sum of $a$ and $b$ to $S$.
Here, the carry-less decimal sum of $6$-digit numbers $a$ and $b$ is the unique $6$-digit number $c$ satisfying the following.
- For every positive integer $d$ less than or equal to $6$, the following $2$ numbers are equal.
- The remainder when the sum of the number represented by the $d$-th character from the left of $a$ and the number represented by the $d$-th character from the left of $b$ is divided by $10$.
- The number represented by the $d$-th character from the left of $c$.
Input
The input is given from standard input in $6$ lines in the following format:
- For every positive integer $i$ less than or equal to $6$, $A_i$ is given on line $i$.
$A_1$ $A_2$ $A_3$ $A_4$ $A_5$ $A_6$
Constraints
The input satisfies the following constraints:
- For every positive integer $i$ less than or equal to $6$, $A_i$ is a $6$-digit number.
Output
Print on $1$ line the maximum possible number of elements of $S$ when $S$ is updated by repeating the operation specified in the problem statement any number of times.
Print a newline at the end.
Sample
Sample 1
Input
000000 000000 000000 000000 000000 000002
As in this case, some of the inputs may coincide.
Output
5
Initially, $S$ is given as $\{000000,000002\}$.
First, choose both elements $a$ and $b$ of $S$ as $000002$ and add the carry-less decimal sum $000004$ of $a$ and $b$ to $S$; then $S$ becomes $\{000000,000002,000004\}$.
Next, choose elements $a$ and $b$ of $S$ as $000002$ and $000004$, respectively, and add the carry-less decimal sum $000006$ of $a$ and $b$ to $S$; then $S$ becomes $\{000000,000002,000004,000006\}$.
Further, choose elements $a$ and $b$ of $S$ as $000004$ and $000004$, respectively, and add the carry-less decimal sum $000008$ of $a$ and $b$ to $S$; then $S$ becomes $\{000000,000002,000004,000006,000008\}$.
At this point, the number of elements of $S$ is $5$. No matter how the original $S$ is operated on, the number of elements cannot be made greater than $5$.
Sample 2
Input
500000 050000 005000 000500 000050 000005
Output
64
By repeating the operation on $S$, it is possible to add to $S$ all $6$-digit numbers in which each digit is $0$ or $5$. For example, $000000$ is obtained as the carry-less decimal sum of $000005$ and $000005$, and $000505$ is obtained as the carry-less decimal sum of $000500$ and $000005$.
Conversely, the elements that can be added by repeating the operation on $S$ are limited to such $6$-digit numbers. Therefore, the maximum possible number of elements of $S$ is the total count $2^6 = 64$ of $6$-digit numbers in which each digit is $0$ or $5$.
Sample 3
Input
100000 010000 001000 000100 000010 000001
Output
1000000
By repeating the operation on $S$, it is possible to add all $6$-digit numbers to $S$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
hamamu