E. Roma and Poker

Codeforces

IDCF803E

Time2000ms

Memory256MB

Difficulty—

dpgraphs

English · Original

Chinese · Translation

Formal · Original

Each evening Roma plays online poker on his favourite website. The rules of poker on this website are a bit strange: there are always two players in a hand, there are no bets, and the winner takes 1 virtual bourle from the loser. Last evening Roma started to play poker. He decided to spend no more than _k_ virtual bourles — he will stop immediately if the number of his loses exceeds the number of his wins by _k_. Also Roma will leave the game if he wins enough money for the evening, i.e. if the number of wins exceeds the number of loses by _k_. Next morning Roma found a piece of paper with a sequence on it representing his results. Roma doesn't remember the results exactly, and some characters in the sequence are written in a way such that it's impossible to recognize this character, so Roma can't recall whether he won _k_ bourles or he lost. The sequence written by Roma is a string _s_ consisting of characters _W_ (Roma won the corresponding hand), _L_ (Roma lost), _D_ (draw) and _?_ (unknown result). Roma wants to restore any _valid_ sequence by changing all _?_ characters to _W_, _L_ or _D_. The sequence is called _valid_ if all these conditions are met: * In the end the absolute difference between the number of wins and loses is equal to _k_; * There is no hand such that the absolute difference before this hand was equal to _k_. Help Roma to restore any such sequence. ## Input The first line contains two numbers _n_ (the length of Roma's sequence) and _k_ (1 ≤ _n_, _k_ ≤ 1000). The second line contains the sequence _s_ consisting of characters _W_, _L_, _D_ and _?_. There are exactly _n_ characters in this sequence. ## Output If there is no _valid_ sequence that can be obtained from _s_ by replacing all _?_ characters by _W_, _L_ or _D_, print _NO_. Otherwise print this sequence. If there are multiple answers, print any of them. [samples]

每天晚上，Roma 都在他最喜欢的网站上玩在线扑克。这个网站的扑克规则有些特别：每局总是两名玩家，没有下注，赢家从输家那里赢得 1 虚拟布尔。昨晚，Roma 开始玩扑克。他决定最多只花 #cf_span[k] 虚拟布尔——如果他的输局数超过赢局数达到 #cf_span[k]，他会立即停止。此外，如果他的赢局数超过输局数达到 #cf_span[k]，他也会离开游戏，因为他已经赢够了今晚的钱。第二天早上，Roma 找到一张写有序列的纸，记录了他的比赛结果。Roma 不记得确切的结果，序列中有些字符书写模糊，无法辨认，因此他无法确定自己是赢了还是输了。 Roma 写下的序列是一个字符串 #cf_span[s]，由字符 _W_（Roma 赢了该局）、_L_（Roma 输了）、_D_（平局）和 _?_（未知结果）组成。Roma 希望通过将所有 _?_ 字符替换为 _W_、_L_ 或 _D_ 来恢复任意一个 _有效_ 序列。一个序列被称为 _有效_，当且仅当满足以下所有条件：帮助 Roma 恢复任意一个这样的序列。第一行包含两个数字 #cf_span[n]（Roma 序列的长度）和 #cf_span[k]（#cf_span[1 ≤ n, k ≤ 1000]）。第二行包含一个由字符 _W_、_L_、_D_ 和 _?_ 组成的序列 #cf_span[s]。该序列恰好包含 #cf_span[n] 个字符。如果无法通过将所有 _?_ 字符替换为 _W_、_L_ 或 _D_ 得到任何 _有效_ 序列，请输出 _NO_。否则，请输出这样一个序列。如果有多个答案，输出任意一个即可。 ## Input 第一行包含两个数字 #cf_span[n]（Roma 序列的长度）和 #cf_span[k]（#cf_span[1 ≤ n, k ≤ 1000]）。第二行包含一个由字符 _W_、_L_、_D_ 和 _?_ 组成的序列 #cf_span[s]。该序列恰好包含 #cf_span[n] 个字符。 ## Output 如果无法通过将所有 _?_ 字符替换为 _W_、_L_ 或 _D_ 得到任何 _有效_ 序列，请输出 _NO_。否则，请输出这样一个序列。如果有多个答案，输出任意一个即可。 [samples]

**Definitions** Let $ n, k \in \mathbb{Z}^+ $ with $ 1 \leq n, k \leq 1000 $. Let $ s \in \{W, L, D, ?\}^n $ be the input sequence of length $ n $. **Constraints** Let $ s' \in \{W, L, D\}^n $ be a sequence obtained by replacing each $ ? $ in $ s $ with $ W $, $ L $, or $ D $. Define the cumulative difference at position $ i $ as: $$ d_i = (\text{number of } W \text{ in } s'[1:i]) - (\text{number of } L \text{ in } s'[1:i]) $$ The sequence $ s' $ is *valid* if: 1. For all $ i \in \{1, \dots, n\} $, $ |d_i| < k $. 2. If $ |d_i| = k $ for some $ i \leq n $, then $ d_i = k $ or $ d_i = -k $, and this occurs **only** at the final position $ i = n $ (i.e., the game stops exactly when $ |d_n| = k $, and not earlier). **Objective** Find any valid $ s' $, or output "NO" if none exists.

Samples

Input #1

3 2
L??

Output #1

LDL

Input #2

3 1
W??

Output #2

NO

Input #3

20 5
?LLLLLWWWWW?????????

Output #3

WLLLLLWWWWWWWWLWLWDW

API Response (JSON)

{
  "problem": {
    "name": "E. Roma and Poker",
    "description": {
      "content": "Each evening Roma plays online poker on his favourite website. The rules of poker on this website are a bit strange: there are always two players in a hand, there are no bets, and the winner takes 1 v",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF803E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Each evening Roma plays online poker on his favourite website. The rules of poker on this website are a bit strange: there are always two players in a hand, there are no bets, and the winner takes 1 v...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "每天晚上，Roma 都在他最喜欢的网站上玩在线扑克。这个网站的扑克规则有些特别：每局总是两名玩家，没有下注，赢家从输家那里赢得 1 虚拟布尔。\n\n昨晚，Roma 开始玩扑克。他决定最多只花 #cf_span[k] 虚拟布尔——如果他的输局数超过赢局数达到 #cf_span[k]，他会立即停止。此外，如果他的赢局数超过输局数达到 #cf_span[k]，他也会离开游戏，因为他已经赢够了今晚的钱。\n\n...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, k \\leq 1000 $.  \nLet $ s \\in \\{W, L, D, ?\\}^n $ be the input sequence of length $ n $.  \n\n**Constraints**  \nLet $ s' \\in \\{W, L, D\\}^n ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments