C. Santa Claus and Robot

Codeforces

IDCF748C

Time2000ms

Memory256MB

Difficulty—

constructive algorithmsmath

English · Original

Chinese · Translation

Formal · Original

Santa Claus has Robot which lives on the infinite grid and can move **along its lines**. He can also, having a sequence of _m_ points _p_1, _p_2, ..., _p__m_ with integer coordinates, do the following: denote its initial location by _p_0. First, the robot will move from _p_0 to _p_1 along one of the shortest paths between them (please notice that since the robot moves only along the grid lines, there can be several shortest paths). Then, after it reaches _p_1, it'll move to _p_2, again, choosing one of the shortest ways, then to _p_3, and so on, until he has visited all points in the given order. Some of the points in the sequence may coincide, in that case Robot will visit that point several times according to the sequence order. While Santa was away, someone gave a sequence of points to Robot. This sequence is now lost, but Robot saved the protocol of its unit movements. Please, find the minimum possible length of the sequence. ## Input The first line of input contains the only positive integer _n_ (1 ≤ _n_ ≤ 2·105) which equals the number of unit segments the robot traveled. The second line contains the movements protocol, which consists of _n_ letters, each being equal either _L_, or _R_, or _U_, or _D_. _k_\-th letter stands for the direction which Robot traveled the _k_\-th unit segment in: _L_ means that it moved to the left, _R_ — to the right, _U_ — to the top and _D_ — to the bottom. Have a look at the illustrations for better explanation. ## Output The only line of input should contain the minimum possible length of the sequence. [samples] ## Note The illustrations to the first three tests are given below. ![image](https://espresso.codeforces.com/832fb8f97a482be815e0f87edde26c9791a0d330.png) ![image](https://espresso.codeforces.com/119a8ba68772b2c2bf76f2acdc58027f6c5cde1f.png) ![image](https://espresso.codeforces.com/c7b4534f24cbad48148bcba24bc44f37bf7a2dbf.png) The last example illustrates that each point in the sequence should be counted as many times as it is presented in the sequence.

圣诞老人有一个机器人，它生活在无限网格上，可以沿着网格线移动。他还可以给机器人一个由 #cf_span[m] 个整数坐标点组成的序列 #cf_span[p1, p2, ..., pm]，并让机器人执行以下操作：设其初始位置为 #cf_span[p0]。首先，机器人会从 #cf_span[p0] 沿着它们之间的一条最短路径移动到 #cf_span[p1]（请注意，由于机器人只能沿网格线移动，因此可能存在多条最短路径）。然后，在到达 #cf_span[p1] 后，它会继续移动到 #cf_span[p2]，同样选择一条最短路径，接着移动到 #cf_span[p3]，依此类推，直到按顺序访问完所有给定点。序列中的某些点可能重复，此时机器人将根据序列顺序多次访问该点。当圣诞老人外出时，有人给机器人提供了一个点序列。这个序列现在丢失了，但机器人保存了其单位移动的协议。请找出该序列的最小可能长度。输入的第一行包含一个正整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 2·105]），表示机器人移动的单位线段数量。第二行包含移动协议，由 #cf_span[n] 个字母组成，每个字母为 _L_、_R_、_U_ 或 _D_ 之一。第 #cf_span[k] 个字母表示机器人在第 #cf_span[k] 个单位线段中移动的方向：_L_ 表示向左，_R_ 表示向右，_U_ 表示向上，_D_ 表示向下。请参考图示以获得更清晰的解释。输出仅一行，包含序列的最小可能长度。前三个测试用例的图示如下。最后一个示例说明，序列中的每个点都应根据其在序列中出现的次数被重复计数。 ## Input 输入的第一行包含一个正整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 2·105]），表示机器人移动的单位线段数量。第二行包含移动协议，由 #cf_span[n] 个字母组成，每个字母为 _L_、_R_、_U_ 或 _D_ 之一。第 #cf_span[k] 个字母表示机器人在第 #cf_span[k] 个单位线段中移动的方向：_L_ 表示向左，_R_ 表示向右，_U_ 表示向上，_D_ 表示向下。请参考图示以获得更清晰的解释。 ## Output 输出仅一行，包含序列的最小可能长度。 [samples] ## Note 前三个测试用例的图示如下。最后一个示例说明，序列中的每个点都应根据其在序列中出现的次数被重复计数。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of unit moves. Let $ D = (d_1, d_2, \dots, d_n) \in \{L, R, U, D\}^n $ be the movement protocol. Let $ P = (p_0, p_1, \dots, p_m) $ be a sequence of points in $ \mathbb{Z}^2 $, where $ p_0 $ is the initial position, and each $ p_i $ for $ i \geq 1 $ is a target point the robot must reach in order. The robot moves from $ p_{i-1} $ to $ p_i $ along a shortest path (Manhattan path) using only horizontal and vertical unit steps. **Constraints** 1. The total number of unit steps in all shortest paths from $ p_{i-1} $ to $ p_i $, for $ i = 1 $ to $ m $, equals $ n $. 2. Each move in $ D $ corresponds to one unit step in one of the four cardinal directions. **Objective** Find the minimum possible value of $ m $, the length of the sequence $ P $, such that there exists a decomposition of $ D $ into $ m $ contiguous subsequences, each corresponding to a shortest path from $ p_{i-1} $ to $ p_i $, for $ i = 1, \dots, m $. Equivalently: Minimize $ m $ such that the entire movement sequence $ D $ can be partitioned into $ m $ segments, where each segment is a shortest path between its start and end point (i.e., no backtracking in net displacement).

Samples

Input #1

4
RURD

Output #1

Input #2

6
RRULDD

Output #2

Input #3

26
RRRULURURUULULLLDLDDRDRDLD

Output #3

Input #4

3
RLL

Output #4

Input #5

4
LRLR

Output #5

API Response (JSON)

{
  "problem": {
    "name": "C. Santa Claus and Robot",
    "description": {
      "content": "Santa Claus has Robot which lives on the infinite grid and can move **along its lines**. He can also, having a sequence of _m_ points _p_1, _p_2, ..., _p__m_ with integer coordinates, do the following",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF748C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Santa Claus has Robot which lives on the infinite grid and can move **along its lines**. He can also, having a sequence of _m_ points _p_1, _p_2, ..., _p__m_ with integer coordinates, do the following...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "圣诞老人有一个机器人，它生活在无限网格上，可以沿着网格线移动。他还可以给机器人一个由 #cf_span[m] 个整数坐标点组成的序列 #cf_span[p1, p2, ..., pm]，并让机器人执行以下操作：设其初始位置为 #cf_span[p0]。首先，机器人会从 #cf_span[p0] 沿着它们之间的一条最短路径移动到 #cf_span[p1]（请注意，由于机器人只能沿网格线移动，因此可能...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of unit moves.  \nLet $ D = (d_1, d_2, \\dots, d_n) \\in \\{L, R, U, D\\}^n $ be the movement protocol.  \nLet $ P = (p_0, p_1, \\dots, p_m) $ be a ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments