Это легкая версия задачи. Единственное отличие заключается в том, что в этой версии \(k \le n\). Вы можете делать взломы только в том случае, если обе версии задачи решены.
Дан прямоугольник размером \(w \times h\) на плоскости \(Oxy\), с точками \((0, 0)\) в нижнем левом углу и \((w, h)\) в верхнем правом углу прямоугольника.
У вас также есть робот, изначально находящийся в точке \((0, 0)\), и сценарий \(s\) из \(n\) символов. Каждый символ является L, R, U или D, что указывает роботу двигаться влево, вправо, вверх или вниз соответственно.
Робот может двигаться только внутри прямоугольника; в противном случае он изменит сценарий \(s\) следующим образом:
- Если он пытается выйти за вертикальную границу, он меняет все символы L на R (и наоборот, все R на L).
- Если он пытается выйти за горизонтальную границу, он меняет все символы U на D (и наоборот, все D на U).
Затем он продолжит двигаться, следуя измененному сценарию, начиная с того символа, который не смог выполнить.
Пример процесса движения робота, \(s = \texttt{"ULULURD"}\) Сценарий \(s\) будет выполняться \(k\) раз подряд. Все изменения в строке \(s\) будут сохраняться даже при повторении. В процессе выполнения, сколько раз робот переместится в точку \((0, 0)\)? Обратите внимание, что начальная позиция не учитывается.
Выходные данные
Для каждого набора входных данных выведите одно целое число — количество раз, когда робот переместится в \((0, 0)\) при выполнении сценария \(s\) \(k\) раз подряд.
Примечание
В первом наборе входных данных робот движется только вверх и вправо. В конце он занимает позицию \((2, 2)\), но никогда не посещает \((0, 0)\). Поэтому ответ равен \(0\).
Во втором наборе входных данных каждый раз при выполнении сценария робот посещает начало координат дважды. И поскольку \(k=2\), он посещает начало координат \(2 \cdot 2 = 4\) раза в общей сложности.
В третьем наборе входных данных визуализация показана ниже:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 2 2 2
UR
4 2 1 1
LLDD
6 3 3 1
RLRRRL
5 5 3 3
RUURD
7 5 3 4
RRDLUUU
|
0
4
3
0
1
|