← 返回题目列表

Codeforces · 771/B

B. 熊和不同的名字

中文机器翻译题面 查看原题

在军队中,要组建一支能在战场上发挥作用的士兵队伍并不容易。沟通至关重要,因此任何两个士兵都不应该共用一个名字(如果他们收到鲍勃是侦察员的命令,如果有两个鲍勃,会发生什么?)。

一组士兵有效当且仅当他们的名字不同时。例如,组(John、Bob、Limak)会有效,而组(Gary、Bob、Gary)和(Alice、Alice)则不会。

你是敌方阵营的间谍。你注意到 n 个士兵站成一排,编号为 1 到 n。将军想要选择一组连续的 k 个士兵。对于每 k 个连续的士兵,将军写下他们是否是一个有效的团队。

你成功窃取了将军的笔记,其中包含 n - k + 1 个字符串 s1、s2、...、sn - k + 1,每个字符串要么是“是”,要么是“否”。

- 字符串 s1 描述一组士兵 1 到 k(如果该组有效,则为“YES”,否则为“NO”)。
- 字符串 s2 描述一组士兵 2 到 k + 1。
- 依此类推,直到字符串 sn - k + 1 描述一组士兵 n - k + 1 到 n。

你的任务是找到 n 个士兵的可能名字。姓名应与被盗笔记相符。每个名称应该是由 1 到 10 个英文字母组成的字符串(含 1 到 10 个英文字母)。第一个字母应为大写,所有其他字母应为小写。名称不必是现有名称 - 例如,可以打印“Xyzzzdj”或“T”。

查找并打印任何解决方案。可以证明,总是存在至少一个解。

输入

输入的第一行包含两个整数 n 和 k (2 ≤ k ≤ n ≤ 50)——分别是士兵的数量和团体的规模。

第二行包含n - k + 1个字符串s1,s2,...,sn - k + 1。如果第i到i + k - 1组士兵有效,则字符串si为“YES”,否则为“NO”。

输出

找到满足所有给定条件的任何解决方案。在一行中打印 n 个空格分隔的字符串,表示顺序中士兵的可能名称。每个名称的第一个字母应大写,其他字母应小写。每个名称只能包含英文字母,长度为 1 到 10。

如果有多个有效的解决方案,则打印其中任何一个。

示例

输入 #1

8 3
NO NO YES YES YES NO

输出 #1

Adam Bob Bob Cpqepqwer Limak Adam Bob Adam

输入 #2

9 8
YES NO

输出 #2

R Q Ccccccccc Ccocc Ccc So Strong Samples Ccc

输入 #3

3 2
NO NO

输出 #3

Na Na Na

注意

在第一个样本中,有 8 名士兵。每连续 3 个,我们就知道他们是否是一个有效的群体。让我们分析一下提供的示例输出:

- 前三名士兵(即 Adam、Bob、Bob)不会是一个有效的团队,因为有两个 Bob。事实上,字符串 s1 是“NO”。
- 士兵 2 到 4(Bob、Bob、Cpqepqwer)也不会有效,并且字符串 s2 为“NO”。
- 士兵 3 到 5(Bob、Cpqepqwer、Limak)将有效,并且字符串 s3 为“YES”。
- ...,
- 士兵 6 到 8(Adam、Bob、Adam)不会有效,字符串 s6 为“NO”。