2015-16 Woburn Challenge Finals - Senior Division
Problem 3: Driving Range
With intel from the Sacred Tree stolen by hydrated bovine spies, times are getting ever more desperate for the monkeys. The Head-Monkey has decided it's time to send out her own elite special agent – Agent Tiny. Tiny has been ordered to journey to Old MacDonald's farm and perform a precision strike against the cows' military headquarters. For this extremely dangerous mission, Tiny is being outfitted with a sophisticated piece of monkey technology – a fully functional car made of branches and leaves, and powered by banana juice. This car will offer him more than enough speed and maneuverability to infiltrate the barn. Also, it can shoot missiles from its front headlights.
In an effort to ensure that Tiny actually accomplishes something useful with his car in the field, the Head-Monkey has instructed him to take it for a spin on the monkeys' specialized driving course. The course will take place in a very large room, which can be represented as a 2D grid of cells, with some targets on the walls. The rows are numbered in increasing order from North to South (starting from 1), and similarly the columns are numbered in increasing order from West to East. Tiny will be required to drive around and fire missiles at all of the targets.
Tiny will start in the Northwestern-most cell (in the first row and first column), with his car facing South. Each second, he may either drive to an adjacent cell, or fire a missile in the direction that his car is currently facing. If he chooses to drive, he may do so in one of the four cardinal directions (North, South, East, or West) as long as he stays within the room (he can't drive North from row 1 or West from column 1), and his car will be left facing the direction in which he just drove.
The Head-Monkey will add N (1 ≤ N ≤ 105) targets to the course, one after another, and make Tiny complete the current course after each one is added. Each time, Tiny will have to start in the Northwestern-most cell and hit all of the targets which have been added so far with missiles, in any order. That is, he will have to complete the course N separate times, and on his i-th run, he'll be required to hit targets 1..i.
The i-th target's position is described by a character Di (either "
R" or "
C") and an integer Pi (1 ≤ Pi ≤ 109). If Di = "
R", then the i-th target is at the far East end of row Pi, meaning that it can be hit by firing a missile Eastward from any cell on row Pi. Otherwise if Di = "
C", then the i-th target is instead at the far South end of column Pi. No two targets are at the same location.
To help convince the Head-Monkey of Tiny's driving skills, can you help Tiny determine how quickly the course can be completed each of the N times?
In test cases worth 4/19 of the points, N ≤ 10 and Pi ≤ 10.
In test cases worth another 7/19 of the points, N ≤ 40 and Pi ≤ 40.
The first line of input consists of a single integer N.
The next N lines each consist of a character and integer Di and Pi, separated by a space, for i = 1..N.
Output N lines, one integer per line. The i-th line of output (for i = 1..N) should consist of the minimum number of seconds required to complete the course for the i-th time.
Sample Input 1
3 R 3 C 2 C 3
Sample Output 1
4 6 8
Sample Explanation 1
The third and final time that Tiny completes the course, one optimal sequence of actions that he can take is as follows:
- Drive East
- Drive South
- Fire a missile (hitting target 2)
- Drive East
- Drive South
- Fire a missile (hitting target 3)
- Drive East
- Fire a missile (hitting target 1)
Sample Input 2
2 R 1 R 10
Sample Output 2
Point Value: 15 (partial)
Time Limit: 3.00s
Memory Limit: 32M
Added: May 07, 2016
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3