In the town of Gnir, there is one circular bus line served by one bus. From each station, the bus driver can drive to any of the two adjacent stations, or spend some time at the current station. During that time, exactly one person arrives at a random station, and waits for the bus in order to go to some other random station. Via an app, the bus driver knows about every person currently waiting anywhere along the route where they need to go. The bus driver chooses how many and who will board the bus at the current station, but the number of passengers may not exceed the bus capacity. The passengers leave the bus as soon as it arrives at their destination. The aim of the bus driver is to minimize the total number of people waiting at all the stations on average over time.

circle

Your task is to tell the bus driver which way to go to achieve this aim. This is complicated by the fact that the passenger capacity of the bus may be small compared to the number of stations.

One simple strategy is to always move in the same direction. Another strategy is to consistently move towards the destination of a particular passenger (e.g. the one who has been on the bus longest).

Can you do better?

Go to instructions.

Advertisements