B. Bear and Different Names

Codeforces

IDCF771B

Time1000ms

Memory256MB

Difficulty—

constructive algorithmsgreedy

English · Original

Chinese · Translation

Formal · Original

In the army, it isn't easy to form a group of soldiers that will be effective on the battlefield. The communication is crucial and thus no two soldiers should share a name (what would happen if they got an order that Bob is a scouter, if there are two Bobs?). A group of soldiers is effective if and only if their names are different. For example, a group (John, Bob, Limak) would be effective, while groups (Gary, Bob, Gary) and (Alice, Alice) wouldn't. You are a spy in the enemy's camp. You noticed _n_ soldiers standing in a row, numbered 1 through _n_. The general wants to choose a group of _k_ consecutive soldiers. For every _k_ consecutive soldiers, the general wrote down whether they would be an effective group or not. You managed to steal the general's notes, with _n_ - _k_ + 1 strings _s_1, _s_2, ..., _s__n_ - _k_ + 1, each either "_YES_" or "_NO_". * The string _s_1 describes a group of soldiers 1 through _k_ ("_YES_" if the group is effective, and "_NO_" otherwise). * The string _s_2 describes a group of soldiers 2 through _k_ + 1. * And so on, till the string _s__n_ - _k_ + 1 that describes a group of soldiers _n_ - _k_ + 1 through _n_. Your task is to find possible names of _n_ soldiers. Names should match the stolen notes. Each name should be a string that consists of between 1 and 10 English letters, inclusive. The first letter should be uppercase, and all other letters should be lowercase. Names don't have to be existing names — it's allowed to print "_Xyzzzdj_" or "_T_" for example. Find and print any solution. It can be proved that there always exists at least one solution. ## Input The first line of the input contains two integers _n_ and _k_ (2 ≤ _k_ ≤ _n_ ≤ 50) — the number of soldiers and the size of a group respectively. The second line contains _n_ - _k_ + 1 strings _s_1, _s_2, ..., _s__n_ - _k_ + 1. The string _s__i_ is "_YES_" if the group of soldiers _i_ through _i_ + _k_ - 1 is effective, and "_NO_" otherwise. ## Output Find any solution satisfying all given conditions. In one line print _n_ space-separated strings, denoting possible names of soldiers in the order. The first letter of each name should be uppercase, while the other letters should be lowercase. Each name should contain English letters only and has length from 1 to 10. If there are multiple valid solutions, print any of them. [samples] ## Note In the first sample, there are 8 soldiers. For every 3 consecutive ones we know whether they would be an effective group. Let's analyze the provided sample output: * First three soldiers (i.e. Adam, Bob, Bob) wouldn't be an effective group because there are two Bobs. Indeed, the string _s_1 is "_NO_". * Soldiers 2 through 4 (Bob, Bob, Cpqepqwer) wouldn't be effective either, and the string _s_2 is "_NO_". * Soldiers 3 through 5 (Bob, Cpqepqwer, Limak) would be effective, and the string _s_3 is "_YES_". * ..., * Soldiers 6 through 8 (Adam, Bob, Adam) wouldn't be effective, and the string _s_6 is "_NO_".

在军队中，组建一支在战场上有效的士兵小组并不容易。沟通至关重要，因此不能有两名士兵拥有相同的名字（如果出现两个 Bob，当下达命令说“Bob 是侦察兵”时会发生什么？）。一个士兵小组是有效的，当且仅当他们的名字互不相同。例如，小组（John, Bob, Limak）是有效的，而小组（Gary, Bob, Gary）和（Alice, Alice）则不是。你是敌方营地中的间谍。你注意到 #cf_span[n] 名士兵排成一排，编号为 #cf_span[1] 到 #cf_span[n]。将军希望选择一组 #cf_span[k] 名连续的士兵。对于每组 #cf_span[k] 名连续的士兵，将军都记录了他们是否构成一个有效的小组。你成功窃取了将军的笔记，其中包含 #cf_span[n - k + 1] 个字符串 #cf_span[s1, s2, ..., sn - k + 1]，每个字符串要么是 "_YES_"，要么是 "_NO_"。你的任务是找出 #cf_span[n] 名士兵可能的名字。这些名字必须与窃取的笔记一致。每个名字应为一个由 #cf_span[1] 到 #cf_span[10] 个英文字符组成的字符串（包含两端），首字母必须大写，其余字母必须小写。名字不必是真实存在的名字 —— 例如允许输出 "_Xyzzzdj_" 或 "_T_"。请找出并打印任意一个可行解。可以证明，至少存在一个解。输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[2 ≤ k ≤ n ≤ 50]），分别表示士兵数量和小组大小。第二行包含 #cf_span[n - k + 1] 个字符串 #cf_span[s1, s2, ..., sn - k + 1]。字符串 #cf_span[si] 为 "_YES_" 表示从第 #cf_span[i] 名到第 #cf_span[i + k - 1] 名士兵组成的小组是有效的，否则为 "_NO_"。请找出满足所有给定条件的任意一个解。在一行中输出 #cf_span[n] 个用空格分隔的字符串，表示按顺序的士兵可能的名字。每个名字的首字母必须大写，其余字母必须小写。每个名字只能包含英文字符，长度在 #cf_span[1] 到 #cf_span[10] 之间。如果有多个有效解，请输出任意一个。 ## Input 输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[2 ≤ k ≤ n ≤ 50]），分别表示士兵数量和小组大小。第二行包含 #cf_span[n - k + 1] 个字符串 #cf_span[s1, s2, ..., sn - k + 1]。字符串 #cf_span[si] 为 "_YES_" 表示从第 #cf_span[i] 名到第 #cf_span[i + k - 1] 名士兵组成的小组是有效的，否则为 "_NO_"。 ## Output 请找出满足所有给定条件的任意一个解。在一行中输出 #cf_span[n] 个用空格分隔的字符串，表示按顺序的士兵可能的名字。每个名字的首字母必须大写，其余字母必须小写。每个名字只能包含英文字符，长度在 #cf_span[1] 到 #cf_span[10] 之间。如果有多个有效解，请输出任意一个。 [samples] ## Note 在第一个样例中，有 #cf_span[8] 名士兵。对于每组 #cf_span[3] 名连续的士兵，我们知道他们是否构成有效的小组。我们分析提供的样例输出：前三个士兵（即 Adam、Bob、Bob）不是有效的小组，因为有两个 Bob。确实，字符串 #cf_span[s1] 是 "_NO_"。第 #cf_span[2] 到第 #cf_span[4] 名士兵（Bob、Bob、Cpqepqwer）也不是有效的，字符串 #cf_span[s2] 是 "_NO_"。第 #cf_span[3] 到第 #cf_span[5] 名士兵（Bob、Cpqepqwer、Limak）是有效的，字符串 #cf_span[s3] 是 "_YES_"。 …… 第 #cf_span[6] 到第 #cf_span[8] 名士兵（Adam、Bob、Adam）不是有效的，字符串 #cf_span[s6] 是 "_NO_"。

**Definitions** Let $ n, k \in \mathbb{Z} $ with $ 2 \leq k \leq n \leq 50 $. Let $ S = (s_1, s_2, \dots, s_{n-k+1}) $ be a sequence of strings, where each $ s_i \in \{\text{"YES"}, \text{"NO"}\} $, indicating whether the group of $ k $ consecutive soldiers starting at position $ i $ is effective. **Constraints** 1. For each $ i \in \{1, \dots, n-k+1\} $: - If $ s_i = \text{"YES"} $, then the $ k $ soldiers at positions $ i, i+1, \dots, i+k-1 $ all have distinct names. - If $ s_i = \text{"NO"} $, then at least two soldiers in positions $ i, i+1, \dots, i+k-1 $ share the same name. 2. Each soldier name is a string of length $ \ell \in [1, 10] $, consisting of English letters, with the first letter uppercase and the rest lowercase. **Objective** Find any sequence of names $ A = (a_1, a_2, \dots, a_n) $ satisfying the above constraints.

Samples

Input #1

8 3
NO NO YES YES YES NO

Output #1

Adam Bob Bob Cpqepqwer Limak Adam Bob Adam

Input #2

9 8
YES NO

Output #2

R Q Ccccccccc Ccocc Ccc So Strong Samples Ccc

Input #3

3 2
NO NO

Output #3

Na Na Na

API Response (JSON)

{
  "problem": {
    "name": "B. Bear and Different Names",
    "description": {
      "content": "In the army, it isn't easy to form a group of soldiers that will be effective on the battlefield. The communication is crucial and thus no two soldiers should share a name (what would happen if they g",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF771B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In the army, it isn't easy to form a group of soldiers that will be effective on the battlefield. The communication is crucial and thus no two soldiers should share a name (what would happen if they g...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在军队中，组建一支在战场上有效的士兵小组并不容易。沟通至关重要，因此不能有两名士兵拥有相同的名字（如果出现两个 Bob，当下达命令说“Bob 是侦察兵”时会发生什么？）。\n\n一个士兵小组是有效的，当且仅当他们的名字互不相同。例如，小组（John, Bob, Limak）是有效的，而小组（Gary, Bob, Gary）和（Alice, Alice）则不是。\n\n你是敌方营地中的间谍。你注意到 #cf...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 2 \\leq k \\leq n \\leq 50 $.  \nLet $ S = (s_1, s_2, \\dots, s_{n-k+1}) $ be a sequence of strings, where each $ s_i \\in \\{\\text{\"YES\"}, \\text{\"NO\"}\\} ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments