問題一覧 > 教育的問題

No.2784 Carry-less Decimal Sum

レベル : / AI推定難易度 : 800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 56
作問者 : 👑 p-adic / テスター : 👑 hamamu
お気に入りにしたユーザー ProblemId : 10514 / 自分の提出
問題文最終更新日: 2024-02-07 21:06:39
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 433 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。