TLE '17 Contest 7 P2 - Airport Hopping

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Joey flying in a plane.

Joey is going to take a vacation in Mexico. He wants to go from Toronto Pearson International Airport YYZ to Cancun International Airport CUN. During the way, he may make multiple stops.

During his trip, he will pass through N airports, starting at YYZ labelled 1 and ending at CUN labelled N. Joey starts at YYZ on day 0 hour 0. There are 24 hours in 1 day.

In total, there are M regularly scheduled flights. Each flight can be described by 3 integers A_i, B_i, C_i, meaning that the flight starts from airport A_i and goes to airport A_i + 1, starting at hour B_i every day, and takes C_i hours to fly to the next airport. Due to slow airport security lines, Joey must wait for 20 minutes before getting on a flight, and 20 minutes after getting off a flight.

In Mexico, there is a celebration of the fire god every hour of the day. Given that he travels optimally, what is the time of the earliest show that Joey can watch?

Input Specification

The first line will contain N (2 \le N \le 10^5), M (N-1 \le M \le 10^6).

The next M lines will contain A_i (1 \le A_i \le N-1), B_i (0 \le B_i \le 23), C_i (1 \le C_i \le 48).

It is guaranteed that it is always possible to fly to Mexico.

Output Specification

Print a single line: Day D Hour H, indicating the time of the earliest show that Joey can watch.

Sample Input 1

2 1
1 1 1

Sample Output 1

Day 0 Hour 3

Sample Explanation 1

Joey arrives at airport 2 at 2:00, and gets off at 2:20.

Sample Input 2

3 3
1 2 10
1 1 48
2 12 1

Sample Output 2

Day 1 Hour 14

Sample Explanation 2

Joey should not take the plane that takes 48 hours as that is too slow.

Joey should arrive at airport 2 at Day 0 Hour 12 using the 10 hour plane, but Joey misses the next flight because he must wait for 20 minutes to pass airport security after getting off the flight, and another 20 minutes to pass security before getting on his next flight.

He gets on the airplane to depart airport 2 on Day 1 Hour 12 and arrives at Mexico at Day 1 Hour 13. Finally gets off the plane at 13:20 and visits the show on Day 1 Hour 14.


Comments

There are no comments at the moment.