103127: [Atcoder]ABC312 Ex - snukesnuke
Description
Score : $600$ points
Problem Statement
Takahashi is going to decide nicknames of $N$ people, person $1,\ldots,N$.
Person $i$ wants a nickname $S_i$. To avoid giving the same nickname to multiple people, he is going to decide their nicknames as follows:
- For each $i=1,\ldots,N$ in order, decide person $i$'s nickname as follows:
- Initialize a variable $k_i$ with $1$.
- Repeatedly increment $k_i$ by one while the $k_i$-time repetition of $S_i$ is someone's nickname.
- Let person $i$'s nickname be the $k_i$-time repetition of $S_i$.
Find $k_1,\ldots$, and $k_N$ after deciding nicknames of the $N$ people.
Constraints
- $N \geq 1$
- $S_i$ is a string of length at least $1$ consisting of lowercase English letters.
- The sum of lengths of $S_i$ is at most $2\times 10^5$.
Input
The input is given from Standard Input in the following format:
$N$ $S_1$ $\vdots$ $S_N$
Output
Print $k_1,\ldots$, and $k_N$ resulting from deciding the nicknames of the $N$ people by the procedure in the problem statement.
Sample Input 1
3 snuke snuke rng
Sample Output 1
1 2 1
- First, he decides person $1$'s nickname.
- Let $k_1=1$.
- The $k_1$-time repetition of $S_1$ is
snuke, which is nobody's nickname, so person $1$'s nickname is set tosnuke.
- Next, he decides person $2$'s nickname.
- Let $k_2=1$.
- The $k_2$-time repetition of $S_2$ is
snuke, which is already a nickname of person $1$, so increment $k_2$ by one to make it $2$. - The $k_2$-time repetition of $S_2$ is
snukesnuke, which is nobody's nickname, so person $2$'s nickname is set tosnukesnuke.
- Finally, he decides person $3$'s nickname.
- Let $k_3=1$.
- The $k_3$-time repetition of $S_3$ is
rng, which is nobody's nickname, so person $3$'s nickname is set torng.
Thus, $k_1$, $k_2$, and $k_3$ result in $1$, $2$, and $1$, respectively.
Sample Input 2
4 aa a a aaa
Sample Output 2
1 1 3 2
- Person $1$'s nickname is set to
aa. - Person $2$'s nickname is set to
a. - Person $3$'s nickname is set to
aaa, becauseaandaaare already nicknames of someone else. - Person $4$'s nickname is set to
aaaaaa, becauseaaais already a nickname of someone else.
Sample Input 3
5 x x x x x
Sample Output 3
1 2 3 4 5
Input
Output
分数：$600$分
问题描述
高桥要给$N$个人，第$1$个人到第$N$个人起昵称。
第$i$个人想要的昵称是$S_i$。为了避免给多个人起相同的昵称，他按照以下方法来决定他们的昵称：
- 按照顺序，对每个人$i=1,\ldots,N$，决定第$i$个人的昵称如下：
- 将变量$k_i$初始化为$1$。
- 当第$k_i$次重复的$S_i$是某人的昵称时，不断将$k_i$加$1$。
- 将第$i$个人的昵称设为第$k_i$次重复的$S_i$。
找出在按照问题描述中的方法为这$N$个人起完昵称后的$k_1,\ldots$和$k_N$。
约束
- $N \geq 1$
- $S_i$是由小写英文字母组成的长度至少为$1$的字符串。
- $S_i$的长度之和最多为$2\times 10^5$。
输入
输入通过标准输入给出，格式如下：
$N$ $S_1$ $\vdots$ $S_N$
输出
按照问题描述中的方法为这$N$个人起完昵称后，打印出$k_1,\ldots$和$k_N$。
样例输入 1
3 snuke snuke rng
样例输出 1
1 2 1
- 首先，他决定第$1$个人的昵称。
- 令$k_1=1$。
- 第$k_1$次重复的$S_1$是
，这不是任何人的昵称，因此第$1$个人的昵称被设为 。
- 接下来，他决定第$2$个人的昵称。
- 令$k_2=1$。
- 第$k_2$次重复的$S_2$是
，这已经是第$1$个人的昵称，因此将$k_2$加$1$使其变为$2$。 - 第$k_2$次重复的$S_2$是
，这不是任何人的昵称，因此第$2$个人的昵称被设为 。
- 最后，他决定第$3$个人的昵称。
- 令$k_3=1$。
- 第$k_3$次重复的$S_3$是
，这不是任何人的昵称，因此第$3$个人的昵称被设为 。
因此，$k_1$，$k_2$和$k_3$分别结果为$1$，$2$和$1$。
样例输入 2
4 aa a a aaa
样例输出 2
1 1 3 2
- 第$1$个人的昵称被设为
。 - 第$2$个人的昵称被设为。
- 第$3$个人的昵称被设为
，因为和 已经是其他人的昵称了。 - 第$4$个人的昵称被设为
，因为 已经是其他人的昵称了。
样例输入 3
5 x x x x x
样例输出 3
1 2 3 4 5