A. Diagonal Walking

Codeforces

IDCF954A

Time1000ms

Memory256MB

Difficulty—

implementation

English · Original

Chinese · Translation

Formal · Original

Mikhail walks on a 2D plane. He can go either up or right. You are given a sequence of Mikhail's moves. He thinks that this sequence is too long and he wants to make it as short as possible. In the given sequence moving up is described by character _U_ and moving right is described by character _R_. Mikhail can replace any pair of consecutive moves _RU_ or _UR_ with a diagonal move (described as character _D_). After that, he can go on and do some other replacements, until there is no pair of consecutive moves _RU_ or _UR_ left. Your problem is to print the minimum possible length of the sequence of moves after the replacements. ## Input The first line of the input contains one integer _n_ (1 ≤ _n_ ≤ 100) — the length of the sequence. The second line contains the sequence consisting of _n_ characters _U_ and _R_. ## Output Print the minimum possible length of the sequence of moves after all replacements are done. [samples] ## Note In the first test the shortened sequence of moves may be _DUD_ (its length is 3). In the second test the shortened sequence of moves can be _UUDRRRDUDDUUU_ (its length is 13).

Mikhail 在二维平面上行走。他只能向上或向右移动。给定一个 Mikhail 的移动序列，他认为这个序列太长了，希望将其尽可能缩短。在给定序列中，向上移动用字符 _U_ 表示，向右移动用字符 _R_ 表示。Mikhail 可以将任意一对连续的移动 _RU_ 或 _UR_ 替换为一个对角线移动（用字符 _D_ 表示）。之后，他可以继续进行其他替换，直到不再存在任何连续的 _RU_ 或 _UR_ 对为止。你的任务是输出经过所有替换后，移动序列的最小可能长度。输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100]) —— 序列的长度。第二行包含由 #cf_span[n] 个字符 _U_ 和 _R_ 组成的序列。请输出经过所有替换后，移动序列的最小可能长度。在第一个测试用例中，缩短后的移动序列可能是 _DUD_（其长度为 #cf_span[3]）。在第二个测试用例中，缩短后的移动序列可以是 _UUDRRRDUDDUUU_（其长度为 #cf_span[13]）。 ## Input 输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 100]) —— 序列的长度。第二行包含由 #cf_span[n] 个字符 _U_ 和 _R_ 组成的序列。 ## Output 请输出经过所有替换后，移动序列的最小可能长度。 [samples] ## Note 在第一个测试用例中，缩短后的移动序列可能是 _DUD_（其长度为 #cf_span[3]）。在第二个测试用例中，缩短后的移动序列可以是 _UUDRRRDUDDUUU_（其长度为 #cf_span[13]）。

**Definitions** Let $ n \in \mathbb{Z} $ be the length of the sequence. Let $ S = s_1 s_2 \dots s_n $ be a string over the alphabet $ \{U, R\} $, representing Mikhail's moves. **Constraints** $ 1 \leq n \leq 100 $ **Objective** Minimize the length of $ S $ by repeatedly replacing any occurrence of consecutive substrings "RU" or "UR" with "D", until no such pair remains. The minimum possible length is: $$ \min \{ |S'| \mid S \xrightarrow{*} S', \text{ where } S' \text{ contains no substring } "RU" \text{ or } "UR" \} $$ Equivalently, the problem reduces to counting the number of **non-adjacent** $ U $ and $ R $ characters after greedily merging all possible adjacent $ U $-$ R $ pairs into $ D $, where each such merge reduces the length by 1. Let $ c_U $ be the number of $ U $'s, and $ c_R $ the number of $ R $'s in $ S $. Each replacement of "UR" or "RU" consumes one $ U $ and one $ R $, producing one $ D $. The maximum number of such replacements is $ \min(c_U, c_R) $. Thus, the minimal length is: $$ n - \min(c_U, c_R) $$

Samples

Input #1

5
RUURU

Output #1

Input #2

17
UUURRRRRUUURURUUU

Output #2

API Response (JSON)

{
  "problem": {
    "name": "A. Diagonal Walking",
    "description": {
      "content": "Mikhail walks on a 2D plane. He can go either up or right. You are given a sequence of Mikhail's moves. He thinks that this sequence is too long and he wants to make it as short as possible. In the 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": "CF954A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Mikhail walks on a 2D plane. He can go either up or right. You are given a sequence of Mikhail's moves. He thinks that this sequence is too long and he wants to make it as short as possible.\n\nIn the g...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Mikhail 在二维平面上行走。他只能向上或向右移动。给定一个 Mikhail 的移动序列，他认为这个序列太长了，希望将其尽可能缩短。\n\n在给定序列中，向上移动用字符 _U_ 表示，向右移动用字符 _R_ 表示。Mikhail 可以将任意一对连续的移动 _RU_ 或 _UR_ 替换为一个对角线移动（用字符 _D_ 表示）。之后，他可以继续进行其他替换，直到不再存在任何连续的 _RU_ 或 _UR...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the length of the sequence.  \nLet $ S = s_1 s_2 \\dots s_n $ be a string over the alphabet $ \\{U, R\\} $, representing Mikhail's moves.\n\n**Constraints**  \n$...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments