2006 Canadian Computing Competition, Stage 2

Day 1, Problem 1: CN Tower

Christy C. Coder is traveling to Waterloo for a programming competition. On the way, she stops in Toronto to do some sightseeing. The unfortunate thing about travelling is that everyone back home expects her to bring back pictures of everything. Christy hates taking pictures: it makes her look like such a tourist! Fortunately, Christy has a plan to make her picture-taking quite painless.

At 553 m tall, CN Tower is the world's tallest free-standing building. 351 m up the tower is the "360" rotating restaurant, which rotates a full 360 degrees every 72 minutes. From there, Christy can see the whole city, and take close-up pictures of all the landmarks using her fancy new 100x optical zoom camera. Since the restaurant itself rotates, she only needs to stand in one place to take pictures in all directions.

The waiters insist that she order something or leave, and Christy is not interested in any of the items on the menu. Therefore, she must act quickly before she gets kicked out. Given the locations of the landmarks of which Christy wants to take a picture, your task is to determine the minimum amount of time that she must spend in the restaurant in order for it to rotate enough to bring all the landmarks in view. Assume that Christy always points her camera exactly perpendicular to the window to minimize distortion due to the glass. Note that multiple landmarks may occupy the same (angular) position, and these landmarks would only require one photograph to capture them.

Since the restaurant staff only realize she is a tourist once she starts taking pictures, we begin measuring the time required once she takes her first picture. Therefore, Christy can move to any position in the restaurant without hassle from the restaurant staff and begin taking pictures from there.


The first line of input is an integer n (2 ≤ n ≤ 1000), the number of landmarks Christy wants to photograph.

Each of the following n lines specify a landmark. Each landmark specification consists of the landmark name (a string of uppercase and lowercase letters of length at most 40 characters), a space, and the compass angle d, in degrees, to the landmark from the CN Tower (0 = north, 90 = east, 180 = south, 270 = west). Note that d is a real number which satisfies 0 ≤ d < 360, with d specified to the hundredth of a degree (i.e., at most two decimal places).


Output a single integer, the minimum number of seconds that Christy must remain in the restaurant. If the time is not an integer number of seconds, round it up to the nearest second (i.e., take the ceiling of the number).

Sample Input

CasaLoma 231.0
OntarioParliament 123.0
SkyDome 75.0
RoyalYorkHotel 340.0
PearsonAirport 165.0

Sample Output


All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Dec 09, 2008

Languages Allowed:

Comments (Search)

Why do we need to know the names of the landmarks?

It's clearly vital to the problem.

for real? or are you being sarcastic?? thanks anyways Jacob, for real. Why is it important if it really is?

Because you have to sort the landmark names in an increasing order...

The starting point is always the one with the lowest alphabetic value duh!

OK, so this seems to be getting a bit silly, because Seyon can't possibly tell that some of us are being sarcastic. Instead of asking whether or not the landmark names are relevant, or why they might be relevant, just write a program, and if you find that landmark names are not relevant, then... you've lost nothing.

What are you talking about Bosco, stop trying to trick Seyon. There's no way you could solve this problem without using the names.

you input them and nothing else. That doesn't qualify as "using" them.

My last 20 or so sumbissions were just me trying to eliminate floating-point inaccuracies because my code worked, but the number got increased by 0.00000000001 and then I used ceil and it rounded up. WATCH OUT FOR THEM, THEY ARE SO ANNOYING

Yes, this is why it's worth 10 points wink.gif
Floating point inaccuracies can be very tricky.
One surefire way out, though, is to just use integers for everything.

woudln't that be really annoying to do?


took me ages to get it