B. Buggy Robot

Codeforces

IDCF888B

Time2000ms

Memory256MB

Difficulty—

greedy

English · Original

Chinese · Translation

Formal · Original

Ivan has a robot which is situated on an infinite grid. Initially the robot is standing in the starting cell (0, 0). The robot can process commands. There are four types of commands it can perform: * _U_ — move from the cell (_x_, _y_) to (_x_, _y_ + 1); * _D_ — move from (_x_, _y_) to (_x_, _y_ - 1); * _L_ — move from (_x_, _y_) to (_x_ - 1, _y_); * _R_ — move from (_x_, _y_) to (_x_ + 1, _y_). Ivan entered a sequence of _n_ commands, and the robot processed it. After this sequence the robot ended up in the starting cell (0, 0), but Ivan doubts that the sequence is such that after performing it correctly the robot ends up in the same cell. He thinks that some commands were ignored by robot. To acknowledge whether the robot is severely bugged, he needs to calculate the maximum possible number of commands that were performed correctly. Help Ivan to do the calculations! ## Input The first line contains one number _n_ — the length of sequence of commands entered by Ivan (1 ≤ _n_ ≤ 100). The second line contains the sequence itself — a string consisting of _n_ characters. Each character can be _U_, _D_, _L_ or _R_. ## Output Print the maximum possible number of commands from the sequence the robot could perform to end up in the starting cell. [samples]

Ivan 有一个机器人，位于一个无限网格上。最初，机器人位于起始单元格 #cf_span[(0, 0)]。机器人可以执行命令，共有四种类型的命令： Ivan 输入了一个包含 #cf_span[n] 个命令的序列，机器人执行了该序列。执行完该序列后，机器人回到了起始单元格 #cf_span[(0, 0)]，但 Ivan 怀疑这个序列在正确执行后并不能让机器人回到原点。他认为有些命令被机器人忽略了。为了确认机器人是否存在严重故障，他需要计算出可能被正确执行的最大命令数。请帮助 Ivan 进行计算！第一行包含一个数字 #cf_span[n] —— Ivan 输入的命令序列长度（#cf_span[1 ≤ n ≤ 100]）。第二行包含该序列本身 —— 一个由 #cf_span[n] 个字符组成的字符串。每个字符可以是 _U_、_D_、_L_ 或 _R_。请输出机器人可能正确执行并最终回到起始单元格的最大命令数。 ## Input 第一行包含一个数字 #cf_span[n] —— Ivan 输入的命令序列长度（#cf_span[1 ≤ n ≤ 100]）。第二行包含该序列本身 —— 一个由 #cf_span[n] 个字符组成的字符串。每个字符可以是 _U_、_D_、_L_ 或 _R_。 ## Output 请输出机器人可能正确执行并最终回到起始单元格的最大命令数。 [samples]

Let $ S \in \{U, D, L, R\}^n $ be a sequence of $ n $ commands. Define the displacement vectors: - $ U = (0, 1) $ - $ D = (0, -1) $ - $ R = (1, 0) $ - $ L = (-1, 0) $ Let $ \vec{p}_i \in \mathbb{Z}^2 $ be the position of the robot after executing the first $ i $ commands. The robot starts at $ \vec{p}_0 = (0, 0) $, and ends at $ \vec{p}_n = (0, 0) $ after executing all $ n $ commands, but some commands may have been ignored. Let $ I \subseteq \{1, 2, \dots, n\} $ be the set of indices of commands that were **performed correctly**. Let $ \vec{v}_I = \sum_{i \in I} \vec{v}_i $ be the total displacement from executing only those commands. We require $ \vec{v}_I = (0, 0) $. **Objective:** Maximize $ |I| $, the number of performed commands, subject to $ \vec{v}_I = (0, 0) $. Equivalently: Find the longest subsequence of $ S $ such that the sum of its corresponding displacement vectors is $ (0, 0) $. Let: - $ u $: number of $ U $ in subsequence - $ d $: number of $ D $ in subsequence - $ r $: number of $ R $ in subsequence - $ l $: number of $ L $ in subsequence Constraints: - $ u - d = 0 \Rightarrow u = d $ - $ r - l = 0 \Rightarrow r = l $ Let $ a = u = d $, $ b = r = l $, then total performed commands = $ 2a + 2b $. Let $ c_U, c_D, c_R, c_L $ be the total counts of each command in $ S $. Then: - $ 0 \leq a \leq \min(c_U, c_D) $ - $ 0 \leq b \leq \min(c_R, c_L) $ Maximize: $ 2a + 2b = 2(a + b) $ Thus, the maximum number of commands that could have been performed correctly is: $$ \boxed{2 \left( \min(c_U, c_D) + \min(c_R, c_L) \right)} $$

Samples

Input #1

4
LDUR

Output #1

Input #2

5
RRRUU

Output #2

Input #3

6
LLRRRR

Output #3

API Response (JSON)

{
  "problem": {
    "name": "B. Buggy Robot",
    "description": {
      "content": "Ivan has a robot which is situated on an infinite grid. Initially the robot is standing in the starting cell (0, 0). The robot can process commands. There are four types of commands it can perform: *",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF888B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Ivan has a robot which is situated on an infinite grid. Initially the robot is standing in the starting cell (0, 0). The robot can process commands. There are four types of commands it can perform:\n\n*...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Ivan 有一个机器人，位于一个无限网格上。最初，机器人位于起始单元格 #cf_span[(0, 0)]。机器人可以执行命令，共有四种类型的命令：\n\nIvan 输入了一个包含 #cf_span[n] 个命令的序列，机器人执行了该序列。执行完该序列后，机器人回到了起始单元格 #cf_span[(0, 0)]，但 Ivan 怀疑这个序列在正确执行后并不能让机器人回到原点。他认为有些命令被机器人忽略了。...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ S \\in \\{U, D, L, R\\}^n $ be a sequence of $ n $ commands.\n\nDefine the displacement vectors:\n- $ U = (0, 1) $\n- $ D = (0, -1) $\n- $ R = (1, 0) $\n- $ L = (-1, 0) $\n\nLet $ \\vec{p}_i \\in \\mathbb{Z}^...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments