Score : $500$ points

问题描述

给定由数字 1 到 9 及字符 X 组成的 $N$ 个字符串 $S_1, S_2, \ldots, S_N$。

我们将选择一个 $(1, 2, \ldots, N)$ 的排列 $P = (P_1, P_2, \ldots, P_N)$ 来构建一个字符串 $T = S_{P_1} + S_{P_2} + \cdots + S_{P_N}$，其中 $+$ 表示字符串的连接操作。

然后，我们计算字符串 $T = T_1T_2\ldots T_{|T|}$（其中 $|T|$ 表示 $T$ 的长度）的“得分”。
得分通过以下 $9$ 步骤从初始分数 $0$ 开始计算：

• 对于满足条件 $1 \leq i < j \leq |T|$, $T_i =$ X, 和 $T_j =$ 1 的整数对 $(i, j)$ 的数量，将 $1$ 分加到得分上。
• 对于满足条件 $1 \leq i < j \leq |T|$, $T_i =$ X, 和 $T_j =$ 2 的整数对 $(i, j)$ 的数量，将 $2$ 分加到得分上。
• 对于满足条件 $1 \leq i < j \leq |T|$, $T_i =$ X, 和 $T_j =$ 3 的整数对 $(i, j)$ 的数量，将 $3$ 分加到得分上。
• $\cdots$
• 对于满足条件 $1 \leq i < j \leq |T|$, $T_i =$ X, 和 $T_j =$ 9 的整数对 $(i, j)$ 的数量，将 $9$ 分加到得分上。

当 $P$ 可以任意选择时，求 $T$ 的最大可能得分。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given $N$ strings $S_1, S_2, \ldots, S_N$ consisting of digits from 1 through 9 and the character X.

We will choose a permutation $P = (P_1, P_2, \ldots, P_N)$ of $(1, 2, \ldots, N)$ to construct a string $T = S_{P_1} + S_{P_2} + \cdots + S_{P_N}$, where $+$ denotes a concatenation of strings.

Then, we will calculate the "score" of the string $T = T_1T_2\ldots T_{|T|}$ (where $|T|$ denotes the length of $T$).
The score is calculated by the following $9$ steps, starting from the initial score $0$:

• Add $1$ point to the score as many times as the number of integer pairs $(i, j)$ such that $1 \leq i \lt j \leq |T|$, $T_i =$ X, and $T_j =$ 1.
• Add $2$ points to the score as many times as the number of integer pairs $(i, j)$ such that $1 \leq i \lt j \leq |T|$, $T_i =$ X, and $T_j =$ 2.
• Add $3$ points to the score as many times as the number of integer pairs $(i, j)$ such that $1 \leq i \lt j \leq |T|$, $T_i =$ X, and $T_j =$ 3.
• $\cdots$
• Add $9$ points to the score as many times as the number of integer pairs $(i, j)$ such that $1 \leq i \lt j \leq |T|$, $T_i =$ X, and $T_j =$ 9.

Find the maximum possible score of $T$ when $P$ can be chosen arbitrarily.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $N$ is an integer.
• $S_i$ is a string of length at least $1$ consisting of digits from 1 through 9 and the character X.
• The sum of lengths of $S_1, S_2, \ldots, S_N$ is at most $2 \times 10^5$.

Input

Input is given from Standard Input in the following format:

$N$

$S_1$

$S_2$

$\vdots$

$S_N$

Output

Print the answer.

Sample Input 1

3
1X3
59
XXX

Sample Output 1

71

When $P = (3, 1, 2)$, we have $T = S_3 + S_1 + S_2 =$ XXX1X359. Then, the score of $T$ is calculated as follows:

• there are $3$ integer pairs $(i, j)$ such that $1 \leq i \lt j \leq |T|$, $T_i =$ X, and $T_j =$ 1;
• there are $4$ integer pairs $(i, j)$ such that $1 \leq i \lt j \leq |T|$, $T_i =$ X, and $T_j =$ 3;
• there are $4$ integer pairs $(i, j)$ such that $1 \leq i \lt j \leq |T|$, $T_i =$ X, and $T_j =$ 5;
• there are $4$ integer pairs $(i, j)$ such that $1 \leq i \lt j \leq |T|$, $T_i =$ X, and $T_j =$ 9.

Therefore, the score of $T$ is $1 \times 3 + 3 \times 4 + 5 \times 4 + 9 \times 4 = 71$, which is the maximum possible value.

Sample Input 2

10
X63X395XX
X2XX3X22X
13
3716XXX6
45X
X6XX
9238
281X92
1XX4X4XX6
54X9X711X1

Sample Output 2

3010

update @ 2024/3/10 11:19:23