As director of the Causality Infraction Agency, your primary objective is track down and arrest unscrupulous individuals attempting to alter the course of history.
Although your mission briefings include the exact year that a time agent must travel to, the physics of time travel don't make it quite so simple. Time travel can only be done by moving through wormholes that connect two specific instances of time together. As a result, an agent must travel through several wormholes in sequence to reach his or her destination time. In addition, an agent may have to spend some time living in the past or future while waiting for the next wormhole to appear. Traveling through a wormhole also isn't as simple as it might seem: moving forward in time through a wormhole will instanteously age the user by a certain number of years and moving backwards through one will instanteously make the traveller slightly younger.
Because the agency pays its agents based on how many years they've aged since joining the service, you are required to minimize the "aging process" as much as possible for every agent. Your goal therefore is to write a program that finds the optimal itinerary of wormhole jumps for each agent's mission and then reports the total number of years each agent will age after completing their assignment.
For agency accounting purposes, the formulas for computing total years aged on a mission are as follows:
- When starting from some year of origin and simply waiting until some destination year, the age a body accumulates in years equals:
destination - origin
In other words, if you were currently in the year 1785 and had to wait until the year 1793, then you will have aged 8 years.
- When traveling forward in time through a wormhole that connects one year of departure with a later year of arrival, then the number of years a body ages is equal to:
floor((arrival - departure) / 2)
Put in another way, you will age half the number of years (rounded down) you normally would have had you instead waited for the equivalent number of years to pass by. Note that when traveling over a small enough time difference, the years aged may be rounded down to zero for accounting purposes.
- When traveling backward in time through a wormhole that connects one year of departure with an earlier year of arrival, then the number of years a body "gains back" by becoming younger is equal to:
floor((departure - arrival) / 4)
In other words, you gain back a quarter of the difference between the two years (rounded down). Note that when traveling over a small enough time difference, the years "gained back" may be rounded down to zero for accounting purposes. - A wormhole that starts and ends at the same year is possible, but causes no aging or time travel, and as such serves little purpose other than to confound the scientists.
Each dataset to this problem will contain a starting year from which all agents begin their travels and a list of mission assignments, one for each agent. Every mission assignment includes a final destination year that the agent must travel to. The mission can only be completed if the agent is able to make a round trip by traveling from the starting year to the mission's destination year and then traveling back to the initial starting year again. If such a round trip cannot be completed, then that particular mission is invalid. For the purposes of this problem, you also do not have to consider the maximum lifespan of any given agent. A mission is considered valid as long as a round trip is possible regardless of how high the count of years aged will be.
