Class Tree
Description This example is based on the "Fast Food" problem, number 662 of volume VI of the ACM programming contests problem set archive. Here, we consider an optimization variant of the problem.

The fastfood chain McBurger owns several restaurants along a highway. Recently, they have decided to build a fixed number of depots along the highway, each one located at a restaurent and supplying several of the restaurants with the needed ingredients. Each of the restaurants will be supplied by the nearest depot. If two or more depots are equidistantly nearest to a restaurant, it is supplied by exactly one of these. The depots should be placed so that the sum of supply distances is minimized.

Input format

Instances are given as facts restaurant(N,K), representing a restaurant named N (this is a constant consisting of lowercase ASCII characters with enclosed underscores), and K is a nonnegative integer less than or equal to 910, representing the kilometer of the highway at which the restaurant is located. Furthermore there is exactly one fact number_depots(N), where N is the number of depots to be built.

Example:
restaurant(auetal_nord,270). number_depots(2).

Output Format

Answer sets should contain the better schema as atoms of the form depot(N,K), where N is the name of the associated restaurant and K the kilometer at which it is located.

NOTES:
1. Issues about directions on the highway (e.g. that some restaurants are reachable only going in one particular direction on the highway) are not considered, it is hence assumed that all restaurants are connected to both directions of the highway.
2. There can be more than one depot at a given kilometer. Actually this is not infrequent, and occurs when there are restaurants on both sides of the highway.

Authors: Wolfgang Faber
Encodings
1 - 1 of 1