ACSL Practice 2009

Task 1: Kansas

The road map of Kansas is a grid where there are straight roads going North to South and straight roads East to West each 1 mile apart. A truck driver gets instructions in the following form: Drive for two hours north at 50 miles per hour, then for 7 hours east at 85 miles per hour, etc. The driver has to take a 1 hour break break after 5 hours of driving. After how many breaks does the driver first pass through or return to the place where he started?

Example 1. Drive for two hours south at 30 miles per hour, then for 4 hours west at 40 miles per hour, then for 3 hours north at 20 miles per hour, then for 6 hours east at 60 miles per hour, then for 5 hours north at 30 miles per hour, and then for 6 hours south at 60 miles per hour.

When following these instructions, the driver will pass through his starting point after taking two breaks. 

Example 2. Drive for 1 hour south at 30 miles per hour, then for 2 hours west at 40 miles per hour, then for 1 hour north at 30 miles per hour, then for 1 hour east at 79 miles per hour, and then for 5 hours north at 30 miles per hour. 

When following these instructions, the driver will not pass through nor return to where he started.

Example 3. Drive for four hours west at 60 miles per hour, then drive for eight hours north at 80 miles per hour, then drive for four hours east at 60 miles per hour, then drive for eight hours south at 100 miles per hour, then drive for ten hours east at 20 miles per hour. 

When following these instructions, the driver will pass through his starting point after taking 4 breaks. 

Input

The input consists of several lines. The first line contains an integer (N ≤ 1000) which is the number of instructions, followed by one line for each instruction, indicating the direction, the number of hours h (1 ≤ h ≤ 200) and the speed s (1 ≤ s ≤ 200) in miles per hour in this order. The geographical directions are indicated by the position of the small hand on an analog clock; 12 stands for north, 6 for south, 9 for west, and 3 for east. 

Output

The output contains a single integer which is the number of breaks taken before the driver first passes through or returns to the place where he started. If the driver does not reach or pass through the place where he started after following all instructions, the output should contain the number -1. 

Sample Input 1

6
6 2 30
9 4 40
12 3 20
3 6 60
12 5 30
6 6 60

Sample Output 1

2

Sample Input 2

5
6 1 30
9 2 40
12 1 30
3 1 79
12 5 30

Sample Output 2

-1

Sample Input 3

5
9 4 60
12 8 80
3 4 60
6 8 100
3 10 20

Sample Output 3

4

All Submissions
Best Solutions


Point Value: 7
Time Limit: 2.00s
Memory Limit: 16M
Added: May 19, 2009

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

Comments (Search)

Is break time (1 hour) included in the time that is provided in the directions.

What I mean is that if he had travelled for five hours, then was told to travel another four hours, would he spend one hour of the next instruction taking a break, then only travelling for the next THREE hours at the provided speed for the next instruction?

This problem is tricky in more than a way; the most part of it is figuring out how to interpret some part of the text and how to write code accordingly.

A shame this entry does not put an author, but I really want to thank you as I had a great time figuring out my solution by trial, error and a lot of pleasant mental exercise :)