Problem A
Artistic Masterpiece
As you know, digital images are often represented as a grid of pixels. Here, let’s assume that we have an infinitely large grid of pixels, with $x$-coordinates and $y$-coordinates ranging from $-\infty $ to $+\infty $. The pixel at $x$-coordinate $x$ and $y$-coordinate $y$ is denoted by $(x, y)$. By the usual convention, the $x$ axis points from the left to the right, and the $y$ axis points from the bottom to the top.
A digital artist decided to create a single-line drawing: once they start drawing, they cannot take their brush off the paper until the drawing is finished.
A brush can be represented as a connected set of pixels. More precisely, the brush that the artist is going to use can be represented by its radius $r$ and a center point $(x_ c, y_ c)$. The set of pixels $(x,y)$ the brush will paint over is
\[ \{ (x, y) \in \mathbb {Z}^2 : (x - x_ c)^2 + (y - y_ c)^4 \leq r\} \]For example, if the brush has a radius $4$ and its center is at pixel $(1, 1)$, the brush will cover all of the following $11$ pixels: $\{ (-1, 1), (0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2), (3, 1)\} $.
Initially, the artist puts the center of their brush on pixel $(0, 0)$. They will move the brush $n$ times according to a string $s$ of length $n$. On the $i$-th move,
-
if $s_ i = \texttt{L}$, the artist moves the brush to the left by $1$ pixel;
-
if $s_ i = \texttt{R}$, the artist moves the brush to the right by $1$ pixel;
-
if $s_ i = \texttt{U}$, the artist moves the brush up by $1$ pixel;
-
if $s_ i = \texttt{D}$, the artist moves the brush down by $1$ pixel.
Note that the brush will paint over all pixels that it covers at any point in time. Furthermore, while the brush is moving, it may paint over the same pixel multiple times.
After the artist finishes drawing, they are curious about the number of pixels that they have painted over. Can you help them?
Input
The first line of input contains two integers $n$ and $r$, denoting the number of moves and the radius of the brush respectively ($0 \leq n \leq 100\, 000$; $1 \leq r \leq 100\, 000$).
The second line of input contains a string $s$ of length $n$, consisting of the characters $\texttt{L}$, $\texttt{R}$, $\texttt{U}$, and $\texttt{D}$, denoting the moves that the artist did.
Output
Output a single integer denoting the number of pixels that the artist has painted over.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 4 RRULDD |
25 |
