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    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.