D. Green and Black Tea

Codeforces

IDCF746D

Time1000ms

Memory256MB

Difficulty—

constructive algorithmsgreedymath

English · Original

Chinese · Translation

Formal · Original

Innokentiy likes tea very much and today he wants to drink exactly _n_ cups of tea. He would be happy to drink more but he had exactly _n_ tea bags, _a_ of them are green and _b_ are black. Innokentiy doesn't like to drink the same tea (green or black) more than _k_ times in a row. Your task is to determine the order of brewing tea bags so that Innokentiy will be able to drink _n_ cups of tea, without drinking the same tea more than _k_ times in a row, or to inform that it is impossible. Each tea bag has to be used exactly once. ## Input The first line contains four integers _n_, _k_, _a_ and _b_ (1 ≤ _k_ ≤ _n_ ≤ 105, 0 ≤ _a_, _b_ ≤ _n_) — the number of cups of tea Innokentiy wants to drink, the maximum number of cups of same tea he can drink in a row, the number of tea bags of green and black tea. It is guaranteed that _a_ + _b_ = _n_. ## Output If it is impossible to drink _n_ cups of tea, print "_NO_" (without quotes). Otherwise, print the string of the length _n_, which consists of characters '_G_' and '_B_'. If some character equals '_G_', then the corresponding cup of tea should be green. If some character equals '_B_', then the corresponding cup of tea should be black. If there are multiple answers, print any of them. [samples]

Innokentiy 非常喜欢喝茶，今天他想恰好喝掉 #cf_span[n] 杯茶。他本想喝更多，但他只有恰好 #cf_span[n] 个茶包，其中 #cf_span[a] 个是绿茶，#cf_span[b] 个是红茶。 Innokentiy 不喜欢连续饮用超过 #cf_span[k] 次同一种茶（绿茶或红茶）。你的任务是确定一个冲泡茶包的顺序，使得 Innokentiy 能够喝掉 #cf_span[n] 杯茶，且不连续饮用同一种茶超过 #cf_span[k] 次；或者告知这是不可能的。每个茶包必须恰好使用一次。第一行包含四个整数 #cf_span[n], #cf_span[k], #cf_span[a] 和 #cf_span[b]（#cf_span[1 ≤ k ≤ n ≤ 10^5]，#cf_span[0 ≤ a, b ≤ n]）— 分别表示 Innokentiy 想要喝的茶杯数、连续饮用同一种茶的最大杯数、绿茶包和红茶包的数量。保证 #cf_span[a + b = n]。如果不可能喝掉 #cf_span[n] 杯茶，请输出 "_NO_"（不含引号）。否则，输出一个长度为 #cf_span[n] 的字符串，由字符 '_G_' 和 '_B_' 组成。若某个字符为 '_G_'，则对应的茶杯为绿茶；若为 '_B_'，则对应的茶杯为红茶。如果有多个答案，输出任意一个即可。 ## Input 第一行包含四个整数 #cf_span[n], #cf_span[k], #cf_span[a] 和 #cf_span[b]（#cf_span[1 ≤ k ≤ n ≤ 10^5]，#cf_span[0 ≤ a, b ≤ n]）— 分别表示 Innokentiy 想要喝的茶杯数、连续饮用同一种茶的最大杯数、绿茶包和红茶包的数量。保证 #cf_span[a + b = n]。 ## Output 如果不可能喝掉 #cf_span[n] 杯茶，请输出 "_NO_"（不含引号）。否则，输出一个长度为 #cf_span[n] 的字符串，由字符 '_G_' 和 '_B_' 组成。若某个字符为 '_G_'，则对应的茶杯为绿茶；若为 '_B_'，则对应的茶杯为红茶。如果有多个答案，输出任意一个即可。 [samples]

**Definitions:** - Let $ n $ be the total number of tea cups to brew. - Let $ k $ be the maximum number of consecutive cups of the same tea type allowed. - Let $ a $ be the number of green tea bags ($ G $). - Let $ b $ be the number of black tea bags ($ B $). - Given: $ a + b = n $. **Constraints:** - The sequence must consist of exactly $ a $ occurrences of $ G $ and $ b $ occurrences of $ B $. - No more than $ k $ consecutive identical characters are allowed. **Objective:** Construct a string $ s \in \{G, B\}^n $ satisfying the above, or output "_NO_" if no such string exists. **Necessary and Sufficient Condition for Feasibility:** Let $ m = \max(a, b) $, $ \ell = \min(a, b) $. The arrangement is possible if and only if: $$ m \leq (k + 1) \cdot (\ell + 1) $$ This ensures that the more frequent tea type can be sufficiently interspersed by the less frequent one without exceeding $ k $ consecutive occurrences. **Output:** - If impossible: "_NO_" - If possible: Any valid string of length $ n $ composed of $ a $ $ G $'s and $ b $ $ B $'s with no run longer than $ k $.

Samples

Input #1

5 1 3 2

Output #1

GBGBG

Input #2

7 2 2 5

Output #2

BBGBGBB

Input #3

4 3 4 0

Output #3

NO

API Response (JSON)

{
  "problem": {
    "name": "D. Green and Black Tea",
    "description": {
      "content": "Innokentiy likes tea very much and today he wants to drink exactly _n_ cups of tea. He would be happy to drink more but he had exactly _n_ tea bags, _a_ of them are green and _b_ are black. Innokenti",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF746D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Innokentiy likes tea very much and today he wants to drink exactly _n_ cups of tea. He would be happy to drink more but he had exactly _n_ tea bags, _a_ of them are green and _b_ are black.\n\nInnokenti...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Innokentiy 非常喜欢喝茶，今天他想恰好喝掉 #cf_span[n] 杯茶。他本想喝更多，但他只有恰好 #cf_span[n] 个茶包，其中 #cf_span[a] 个是绿茶，#cf_span[b] 个是红茶。\n\nInnokentiy 不喜欢连续饮用超过 #cf_span[k] 次同一种茶（绿茶或红茶）。你的任务是确定一个冲泡茶包的顺序，使得 Innokentiy 能够喝掉 #cf_spa...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions:**\n- Let $ n $ be the total number of tea cups to brew.\n- Let $ k $ be the maximum number of consecutive cups of the same tea type allowed.\n- Let $ a $ be the number of green tea bags ($...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments