Editorial for TLE '17 Contest 7 P2 - Airport Hopping
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
First, note that the 20 minute security line means 3 things.
- The earliest flight you can get on is at
Day 0 Hour 1
. - Between any two flights, there must be a single hour gap.
- After the last plane lands in Mexico, Joey must wait for the show that starts 1 hour after he lands.
To codify all this, we start at Day 0 Hour 1
, and each flight we take now suddenly takes an extra hour.
Once we make these changes, we can assume that we transfer between flights instantly, and that we will visit the show that starts as soon as we land.
At each airport, there is only one direction to go, so we take our current time . Let the time of the next flight be , and the time of the flight be .
- If , then we can catch the flight later in the day, so the time to get to the next airport will be .
- If , then we must wait until tomorrow to catch the flight, so the time to get to the next airport will be .
Take all the flights from this airport into account, and pick the shortest way to get to the next airport.
Repeat this process until you get to Mexico, and print out the time you arrive.
Comments