SPOJ.com - Problem ZIGZAG

ZIGZAG - Zig-Zag rabbit

A N×N matrix is filled with numbers 1 to N², diagonally in a zig-zag fashion.

The table 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 ≤ 100 000, 1 ≤ K ≤ 300 000), 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.

Example

Input:
6 8
DDRRUULL

Output:
47

Input:
3 8
DDRRUULL

Output:
41

Input:
6 10
RRRRRDDDDD

Output:
203

Clarification for the first sample: The rabbit visits cells 1, 3, 4, 9, 13, 8, 6, 2 and 1. 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.

Submit solution!

Added by:	Luka Kalinovcic
Date:	2010-08-05
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: NODEJS OBJC PERL6 VB.NET

hide comments

2024-11-27 22:06:29
This task requires a lot of time to debug, but there are two basic concepts
1. The sum of the arithmetic progression
2. Modular arithmetic

You can output the matrix beautifully like this

f(i, 0, n) {
f(j, 0, n) {
printf("%5lld", mat[i][j]);
}
printf("\n");
}

Last edit: 2024-11-27 22:09:13

2019-07-18 18:16:53
What a bitch to generalize! ... so I didn't. But only after 2 hours of trying :/ One of the ugliest if/else mazes I've ever written, still feels good to get past it.

2017-11-09 14:55:04
iterate till ( i < k and i < s.length() ) to avoid WA after 12th tc.

2016-07-04 16:37:08
Ac in 1 go :)

2015-10-28 02:03:46 Advitiya
use unsigned long long for each and every f***ing thing

2015-10-16 21:35:15 enigmus
Watch out for implicit type conversions!!! In c++, if operands are of type int then the result is also of type int before implicit conversion and the result is wrong. To fix it, you can implicitly cast one of your operands. It costed me 3 WA

2015-10-16 20:55:53 enigmus
I've noticed a tiny flaw in problem definition. It is stated that 1 <= N <= 100000 and 1 <= K <= 300000 but that cannot be true because if N == 1 then K must be 0 otherwise the sequence of jumps will leave the matrix.
Although it probably isn't that important

Last edit: 2015-10-16 20:56:15

2015-09-28 23:24:12 monkz
i have used the correct formula and have used unsigned long long .......still its showing WA after 12th case . Any tricky test cases??

Last edit: 2015-09-28 23:24:43

2015-07-01 18:47:21 Bhuvnesh Jain
AC in one go in 0.00 seconds.... easy just calculate the formula for the number on i-row and j-column....
Hint: i used values for summation of n terms for reference

2013-01-08 10:53:25 preetam
make all the input unsigned long long..
got AC... :)

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

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

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