2006 Canadian Computing Competition, Stage 2

Day 2, Problem 1: CN Tower 2

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 elevator normally takes 61 seconds to get from the ground up to the rotating restaurant. Unfortunately, when Christy arrives at the CN Tower, she learns that the elevator is out of service, so she has to take the stairs, which takes somewhat longer. Christy arrives at the top at 9:36 pm, by which time it is dark. She can only take pictures with a very powerful flash, which takes a long time to recharge between pictures. While the flash is charging, she cannot take any pictures. Thus, Christy needs a new program to calculate the minimum time that she must spend in the restaurant in order for it to rotate enough to bring all the landmarks in view, and taking into consideration the charging time of the flash. In addition to these difficulties, the restaurant closes at midnight. Thus, Christy may not have enough time to take pictures of all the landmarks.

As before, assume that Christy does not move around in the restaurant after choosing her initial position, but waits for it to rotate to the angle required to take each picture. As with the daytime problem, Christy can (very quickly) pick her initial position, since the restaurant is not that big. Christy always points her camera exactly perpendicular to the window to minimize distortion due to the glass. After taking the last picture, Christy must stay in the restaurant until her flash recharges. Since it is dark outside, if more than one landmark occupies an angular position, Christy can capture only one one landmark per photo (in order to keep the desired landmark in focus, blurring all others).

Input

The first line of input consists of an integer n (1 ≤ 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), a space, and the compass angle, in degrees (specified with a maximum of 2 decimal places), to the landmark from the CN Tower (0 = north, 90 = east, 180 = south, 270 = west). Finally, the last line contains the amount of time, in seconds, required for the flash to charge.

Output

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. If it is not possible for Christy to take all the pictures before closing, instead output not possible.

Sample Input

5
CasaLoma 231.0
OntarioParliament 123.0
SkyDome 75.0
RoyalYorkHotel 340.0
PearsonAirport 165.0
10

Sample Output

3022

All Submissions
Best Solutions

Point Value: 30
Time Limit: 10.00s
Memory Limit: 16M
Added: Dec 25, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

for the first picture, is her flash already charged or does she have to charge the flash first in order to take her first picture. 

Are you assuming that she took pictures of the stairwell?

I'm rather certain that she enters with a fully charged camera.

For future reference, this is untrue.

can this problem be completed with simple loops or does it recursion and/or dp?

Why not try for yourself?

In the real CCC, nobody would tell you how to solve it, so why expect it here? These problems are for practice. Asking how to solve one just limits your potential gain.

Just take a look at how many points it's worth.

But anyway, you should be able to either try it for yourself, or think about it and figure out how long your planned solution would take (time complexity, O(N) notation!).