ZIGZAG  ZigZag rabbit
A N×N matrix is filled with numbers 1 to N^{2}, diagonally in a zigzag 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 32bit 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.
hide comments
nadstratosfer:
20190718 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. 

sucide:
20171109 14:55:04
iterate till ( i < k and i < s.length() ) to avoid WA after 12th tc. 

rishabhjain996:
20160704 16:37:08
Ac in 1 go :) 

Advitiya:
20151028 02:03:46
use unsigned long long for each and every f***ing thing 

enigmus:
20151016 21:35:15
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 

enigmus:
20151016 20:55:53
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.


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


Bhuvnesh Jain:
20150701 18:47:21
AC in one go in 0.00 seconds.... easy just calculate the formula for the number on irow and jcolumn....


preetam:
20130108 10:53:25
make all the input unsigned long long..


Sachin Railhan:
20120814 19:05:25
Note: Use 64 bit integers. Last edit: 20120814 19:21:21 
Added by:  Luka Kalinovcic 
Date:  20100805 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 VB.NET 