Bridge Placements
Time limit1sMemory limit128 MB
Place k horizontal bridges between two skyscrapers of given heights to minimize total stairs over all ordered floor pairs, breaking ties with the lowest placement.
- Level
Medium7 of 10
- Topics
- Dynamic programming, Greedy, Math, Implementation
- Solved
- No attempts yet
Problem
A large company is planning a new office campus. The campus will consist of two buildings, A and B, and many people are expected to cross from one building to the other during a working day. To spare them from walking all the way down to the ground floor and back up again, the company wants to build some bridges between the buildings.
Write a program that finds the best placement of the bridges. Every bridge is horizontal, connecting floor x of building A to the same floor x of building B. The best placement is the one for which the total number of stairs traversed is smallest, where the total is summed over every possible starting floor in A and ending floor in B. (That is, assume the number of trips from floor x in A to floor y in B equals 1 for every x and y.) Note that even after the bridges are built, a person may still choose to walk down to the ground floor and up the other side if that requires fewer stairs.
Sometimes more than one placement is equally optimal. In those cases, choose the placement whose bridges are as low as possible; thus 1, 2, 3 is preferred to 1, 2, 4, and 1, 8, 9 is preferred to 2, 3, 4.
Input
One or more lines, each containing three positive integers: the heights of the two buildings and the number of bridges.
The input ends with a line containing a single -1.
Output
For each input line, print two lines. The first line contains a single integer: the minimum total number of stairs traversed. The second line lists the floors at which the bridges are placed, in increasing order. The ground floor is written as 0, and the highest floor of a building of height x is x − 1.