Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1633. Matrix
МоделированиеРазбор случаев
Олимпиадные задачи на английском языке
| 04/07/2011 | Лето 2011 - дорешивание (10H) |
| 15/07/2011 | Лето 2011 - 10 (H) |
Ограничения: время – 1s/2s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
A `N\ times\ N` matrix is filled with numbers 1 to `N*N`, diagonally in a zig-zag fashion. The illustration below
shows numbers in the matrix for `N\ =\ 6`.
1 2 6 7 15 16 3 5 8 14 17 26 4 9 13 18 25 27 10 12 19 24 28 33 11 20 23 29 32 34 21 22 30 31 35 36
There is a rabbit in the cell containing number 1. A rabbit can jump to a neighboring cell (up, down,
left or right) if that cell exists.
Given `K` valid rabbit jumps, write a program that will calculate the sum of numbers of all cells that
rabbit visited (add the number to the sum each time rabbit visits the same cell).
Input
The first line contains two integers `N` and `K` (`1\ ≤\ N\ ≤\ 100000`, `1\ ≤\ K\ ≤\ 300000`), the size of the matrix
and the number of rabbit jumps.
The second line contains a sequence of `K` characters 'U', 'D', 'L' and 'R', describing the direction of each
jump. The sequence of jumps will not leave the matrix at any moment.
Output
Output one integer, the sum of numbers on visited cells.
Note: This number doesn't always fit in 32-bit integer type.
Sample Input 1
6 8 DDRRUULL
Sample Output 1
47
Sample Input 2
3 8 DDRRUULL
Sample Output 2
41
Sample Input 3
6 10 RRRRRDDDDD
Sample Output 3
203
Clarification for the second sample: The rabbit visits cells 1, 3, 4, 8, 9, 7, 6, 2 and 1.
Clarification for the third sample: The rabbit visits cells 1, 2, 6, 7, 15, 16, 26, 27, 33, 34 and 36.
Source: School competition, February 2010
