codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

748C.md (2471B)


      1 Source: https://codeforces.com/problemset/problem/748/C
      2 
      3 C. Santa Claus and Robot
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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.
     22 
     23 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.
     24 
     25 Input
     26 
     27 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.
     28 
     29 Output
     30 
     31 The only line of input should contain the minimum possible length of the sequence.
     32 
     33 Examples
     34 
     35 Input
     36 
     37 ```
     38 4  
     39 RURD
     40 ```
     41 
     42 Output
     43 
     44 ```
     45 2
     46 ```
     47 
     48 Input
     49 
     50 ```
     51 6  
     52 RRULDD
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 2
     59 ```
     60 
     61 Input
     62 
     63 ```
     64 26  
     65 RRRULURURUULULLLDLDDRDRDLD
     66 ```
     67 
     68 Output
     69 
     70 ```
     71 7
     72 ```
     73 
     74 Input
     75 
     76 ```
     77 3  
     78 RLL
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 2
     85 ```
     86 
     87 Input
     88 
     89 ```
     90 4  
     91 LRLR
     92 ```
     93 
     94 Output
     95 
     96 ```
     97 4
     98 ```
     99 
    100 Note
    101 
    102 The illustrations to the first three tests are given below.
    103 
    104 ![](https://espresso.codeforces.com/832fb8f97a482be815e0f87edde26c9791a0d330.png) ![](https://espresso.codeforces.com/119a8ba68772b2c2bf76f2acdc58027f6c5cde1f.png) ![](https://espresso.codeforces.com/c7b4534f24cbad48148bcba24bc44f37bf7a2dbf.png)
    105 
    106 The last example illustrates that each point in the sequence should be counted as many times as it is presented in the sequence.