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.

The fastfood chain McBurger owns several restaurants along a highway. Recently, they have decided to build several depots along the highway, each one located at a restaurent and supplying several of the q 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. Naturally, the depots should be placed so that the average distance between a restaurant and its assigned depot is minimized, or, equivalently that the sum of supply distances is minimized.

We are to verify whether a given schema for constructing depots is optimal (among all construction schemas that construct the same number of depots as in the given schema). If it is, then there should not be any answer set; if it is not optimal, answer sets should encode a better solution.

Input format

Instances are given as facts over two relations: 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.

Example:
restaurant(auetal_nord,270).

depot(N,K), representing the fact that a depot is to be constructed at the restaurant named N, located at kilometer K, in the construction schema which is to be checked.

Example:
depot(breisgau_ost,761).

Output Format

Answer sets should contain the better schema as atoms of the form altdepot(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 - 3 of 3