Canadian Computing Competition: 2013 Stage 2, Day 2, Problem 1
Brian the Computer Science Nerd is going on a date with his girlfriend, Anatevka! His romantic location of choice is a movie theatre - but not an IMAX theatre, of course, as that would be far too expensive.
This theatre has close
to the screen, while seats in further rows are considered to be far
.
Over the course of E
indicating a person entering, L
indicating a person leaving, and S
indicating a seating suggestion. All seats involved in the events are valid seats inside the theatre, and every seat that Anatevka suggests will be close
, as she believes that they're the best.
Every time Anatevka makes a suggestion, Brian must, of course, analyze its quality. If either of the two seats she suggests is already occupied, he should explain to her that her recommendation is invalid with a simple No
. Otherwise, he'd like to calculate the total inconvenience of both seats in such an arrangement. The inconvenience of sitting in seat S
representing a suggested seat, and an F
representing a seat within its field of vision:
S | ||||||
F | F | F | ||||
F | F | F | F | F | ||
F | F | F | F | F | F | F |
After all the events have taken place, the movie is about to start, and a final decision must be made on where to sit - and Brian will handle that. He concludes that seats that are far
are clearly superior (as they offer a broader view of the screen), and he knows that the point of going to the movies is to have an optimal viewing experience, so selecting two adjacent seats is certainly not mandatory. As such, he'd like to determine the minimum total inconvenience for any two far
unoccupied seats in the theatre. Note that, if one of the chosen seats is in the other's field of vision, this does not count toward its inconvenience - it's only determined by other people sitting in the theatre.
Input Specification
The first line of each test case contains two integers,
The next
For test cases worth
For test cases worth
Output Specification
For each of Anatevka's suggestions (i.e. when S
in the input), output the string No
if the suggestion is invalid; otherwise, output the total inconvenience of the two suggested seats.
The last line of output should contain the minimum total inconvenience of any pair of far
, unoccupied seats.
Sample Input
3 7
E 1 2
E 2 5
S 3 4
E 2 3
L 2 5
S 1 3
S 2 2
Output for Sample Input
3
0
No
0
Explanation of Output for Sample Input
When Anatevka makes her first suggestion, the front P
represents a person, and an S
represents one of the suggested seats)
S | S | |||
P | ||||
P |
The second suggestion is shown below:
P | ||||
P | S | S |
These two seats aren't obstructed by any people, so their total inconvenience is
Finally, Brian can easily select two far
seats which each have inconvenience far
rows with
Comments
Movie theater with 1e12 seats... Nice :D
watch a movie with ur
girlfriends!!! :DHint
Which data structure do we need for this problem?
Question
Could someone please explain to me how the Field of View works? How is (1,2) in the FOV of (3,5) but (2,5) is not in the FOV of (3,4) ???? The problem description of manhattan distance does not make sense to me, I have looked at what manhattan distance is but I still dont get it