AT_abc312_h [ABC312Ex] snukesnuke

题目描述

高桥君需要为编号为 $1,\ldots,N$ 的 $N$ 个人决定昵称。

第 $i$ 个人希望自己的昵称是 $S_i$。为了避免给多人取相同的昵称，高桥君按照以下步骤为 $N$ 个人决定昵称：

• 按照 $i=1,\ldots,N$ 的顺序，依次为第 $i$ 个人决定昵称：
  • 令变量 $k_i=1$。
  • 只要“将 $S_i$ 重复 $k_i$ 次得到的字符串”已经被某个人作为昵称使用，就将 $k_i$ 增加 $1$ 并继续判断。
  • 将“$S_i$ 重复 $k_i$ 次得到的字符串”作为第 $i$ 个人的昵称。

请你求出为 $N$ 个人决定昵称后得到的 $k_1,\ldots,k_N$。

输入格式

输入按以下格式从标准输入读入。

$N$
$S_1$
$\vdots$
$S_N$

输出格式

请按照题目中的操作，为 $N$ 个人决定昵称后，按顺序用空格分隔输出 $k_1,\ldots,k_N$。

输入输出样例 #1

输入 #1

3
snuke
snuke
rng

输出 #1

1 2 1

输入输出样例 #2

输入 #2

4
aa
a
a
aaa

输出 #2

1 1 3 2

输入输出样例 #3

输入 #3

5
x
x
x
x
x

输出 #3

1 2 3 4 5

说明/提示

限制条件

• $N\geq 1$
• $S_i$ 仅由小写英文字母组成，且长度不少于 $1$
• 所有 $S_i$ 的长度之和不超过 $2\times 10^5$

样例解释 1

• 首先为第 $1$ 个人决定昵称。
  • 令 $k_1=1$。
  • $S_1$ 重复 $k_1$ 次得到的字符串 snuke 还没有被任何人使用，所以第 $1$ 个人的昵称为 snuke。
• 接着为第 $2$ 个人决定昵称。
  • 令 $k_2=1$。
  • $S_2$ 重复 $k_2$ 次得到的字符串 snuke 已经被第 $1$ 个人使用，所以将 $k_2$ 增加到 $2$。
  • $S_2$ 重复 $k_2$ 次得到的字符串 snukesnuke 还没有被任何人使用，所以第 $2$ 个人的昵称为 snukesnuke。
• 最后为第 $3$ 个人决定昵称。
  • 令 $k_3=1$。
  • $S_3$ 重复 $k_3$ 次得到的字符串 rng 还没有被任何人使用，所以第 $3$ 个人的昵称为 rng。

因此，$k_1,k_2,k_3$ 分别为 $1,2,1$。

样例解释 2

• 第 $1$ 个人的昵称为 aa。
• 第 $2$ 个人的昵称为 a。
• 第 $3$ 个人的昵称，a、aa 已经被其他人使用，所以为 aaa。
• 第 $4$ 个人的昵称，aaa 已经被其他人使用，所以为 aaaaaa。

由 ChatGPT 4.1 翻译