Like many cities of the North American Sunbelt, Las Gridas is a big grid of two-way roads (three lanes for each direction), some going east-west and some north-south. Most people get around by driving their cars. But gridlock and energy costs have finally driven the normally car-loving culture to reconsider its disdain for buses.
To go from corner (x,y) to (x',y') one could imagine taking a bus first to (x',y) and then to (x',y'). An alternative is to go first to (x,y') and then to (x',y'). Of course less direct routes involving three or more buses are also possible.
It takes one time unit (about 2.5 minutes) to go from one intersection to another in a dedicated bus lane (or for a car on a traffic-free road).
As the city planner, you would like to make the bus more attractive than the car. Commuter surveys indicate that if you can make any bus trip take at most eight time units more than a traffic-free car trip, then you can convince the public to switch.
For cost and congestion reasons, you want to minimize the number of buses you purchase. You may assume the buses will arrive at each street corner on the second they should.
1. Assume that the same number of east-west and north-south roads. How can you achieve the eight-unit guarantee no matter when a commuter arrives at the bus stop? You can ignore the time to get on and off and to go from one bus to another at the same intersection. (There will be a center island at each intersection where all buses stop.)
Would it be enough to put buses four units apart on each east-west road and four units apart on each north-south road?
Solution to warm-up:
Sure. The commuter would have to wait at most four units at each bus stop. But note that this solution does not take advantage of the dedicated bus lanes or the precise arrival times.
Can you achieve the same guarantee with fewer buses?