8VC Venture Cup 2016 - Elimination Round |
---|
Закончено |
Робот Кельвин находится на бесконечном клетчатом поле. Его исходный код является последовательностью из n команд, каждая из которых это «U», «R», «D», или «L» — указание роботу сдвинуться на одну клетку вверх, вправо, вниз или влево соответственно. Кельвину интересно, сколько различных подстрок (непрерывных подпоследовательностей) строки с командами обладают тем свойством, что, выполнив все команды данной подстроки, Кельвин вернётся в ту же клетку, с которой начинал. Две подстроки считаются различными, если у них отличаются индексы первой или последней позиции.
В первой строке входных данных записано целое число n (1 ≤ n ≤ 200) — длина исходной последовательности команд.
В следующей строке записаны n символов, каждый из которых является «U», «R», «D» или «L» — сама исходная последовательность команд.
Выведите единственное целое число — количество подстрок, выполнение которых оставит Кельвина на месте.
6
URLLDR
2
4
DLUU
0
7
RLRLRLR
12
В первом примере подходит вся строка и подстрока «RL».
Обратите внимание: в третьем примере подстрока «LR» встречается три раза, поэтому и в ответе должна быть учтена тоже три раза.
Название |
---|