ZIGZAG - Zig-Zag rabbit
A N×N matrix is filled with numbers 1 to N2, 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.
hide comments
|
Dima:
2011-05-15 22:04:55
2011-02-16 07:52:48 J Sai Kiran Reddy
|
|
Nikhil:
2011-02-26 00:23:59
i guess there is a special case.. plzz tell... i m getting wrong answer.. |
|
Sai Kiran Reddy Jakka:
2011-02-16 06:52:48
O(k) giving TLE !!!!! |
|
anon:
2010-10-18 01:18:32
Make even MOAR stupid time limits for the rewriting of fp-code on shit imperative |
|
David Gómez:
2010-08-17 01:59:02
@Purvesh No. Write a O(N^2) solution and compare both solutions to see where the problem is. Last edit: 2010-08-17 01:59:25 |
|
Purvesh Karkamkar:
2010-08-14 11:49:40
@David Gomez is there any special case which you handled differently.There must be some particular input which i have not thought about..
|
|
|
David Gómez:
2010-08-10 07:15:46
@anurag Don't keep all that grid in memory ;-). Reduce the number of elements that you need to keep in memory trying to see when a cell can be deduced from any other one. I hope it helps Last edit: 2011-01-07 18:05:44 |
| 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 |
RSS