Competition Programming:
Problem Set 10
Problem A: Choice of hotels
When the organizers of the International Programming Competition reserve
hotels for the teams, they select hotels within walking distance from the
competition site. Your task is to write a program that helps to identify
these hotels on a city map.
Input
The input is a city map, which includes streets, their intersections, and
hotel locations; all streets are two-way, all hotels are located on street
intersections, and no two hotels are on the same intersection. The first
input line contains four positive integers, n, m, k,
and d, separated by single spaces:
-
n is the number of intersections, which is between 2 and 100,000;
-
m is the number of streets, which is between 1 and 1,000,000;
-
k is the number of hotels, which is between 1 and n;
-
d is the maximal acceptable distance from a hotel to the competition,
which is between 1 and 1,000,000.
The next m lines represent streets, one street per line; the description
of a street includes three integers, separated by single spaces, where
the first two integers are the intersections connected by this street,
and the third is the street length. For example, the line "2 4 10"
describes a street between intersections 2 and 4, the length of which is
10. The intersection numbers are between 1 and n, and the street
lengths are between 1 and 1,000. Finally, the last k lines represent
hotels, one hotel per line; the description of a hotel includes an integer
and a string of lower-case letters, with a single space between the integer
and the string. The integer is an intersection number, and the string is
the name of the hotel on this intersection, which contains between 1 and
10 letters. We assume that the competition site is located on intersection
1, and thus we are looking for hotels within distance d from intersection
1.
Output
If the map includes no hotels within distance d from the competition
site, the output is the string "No hotels"; else, the output is
the list of all such hotels in the alphabetical order, one hotel per line.
Sample input
4 4 3 10
1 2 10
1 3 20
2 4 30
3 4 40
1 motel
2 hotel
4 inn
Sample output
hotel
motel
Problem B: Star Trek Optimization
The crew of the Starship Enterprise has received the task to terraform
the planets in a recently discovered solar system. The terraforming of
a planet is a reasonably simple operation, which involves dropping a pack
with special bacteria onto its surface. These bacteria feed on inorganic
materials and produce breathable air; they quickly multiply until covering
the entire planet, and eventually produce enough air to make it inhabitable.
Since bacteria cannot travel in space among planets, the terraforming usually
requires a pack for every planet; however, the planets in this system have
a unique property that allows the use of fewer packs. Specifically, some
planets are connected by wormholes, which are one-way hyperspatial corridors
that allow bacteria to move between planets. If a planet has a wormhole
leading to another planet, and the bacteria terraform the first planet,
then they eventually spread through the wormhole to the second planet and
terraform it as well. Note that a wormhole is a one-way path, which does
not allow bacteria to spread in the opposite direction. Since terraforming
packs are valuable and the process of dropping them is time-consuming,
the crew needs to determine the minimal required number of packs. Your
task is to write a program that helps with this task.
Input
The input is a map of the solar system, which includes planets and wormholes
between them. The first line contains two positive integers, n and
m, separated by a single space; n is the number of planets,
which is between 2 and 100,000, and m is the number of wormholes,
which is between 1 and 1,000,000. The next m lines represent wormholes,
one per line; the description of a wormhole includes two distinct integers
between 1 and n, separated by a single space, where the first integer
is the planet at the beginning of the wormhole, and the second is the planet
at its end. For example, the line "2 4" describes a wormhole from
planet 2 to planet 4.
Output
The output is a single integer, which is the minimal number of packs required
for terraforming all planets.
Sample input
8 6
1 2
2 3
4 5
5 6
6 5
7 3
Sample output
4
Problem C: Cell-phone towers
Since the transmission range of a cellular phone is very small, phone companies
install a large number of transmission towers, which provide coverage for
populated areas; we assume that the range of each tower is ten miles. If
two towers are within twenty miles from each other, then their ranges overlap,
and they need to use different frequencies to avoid interference. On the
other hand, if the distance between two towers is strictly greater than
twenty miles, they may use the same frequency. Your task is to write a
program that determines the minimal number of different frequencies required
for a given set of towers.
Input
The input includes the locations of towers; the first line is the number
of towers, which is between 2 and 100, and the other lines represent specific
towers. The description of a tower includes two positive integers between
1 and 1,000,000, which are its coordinates in miles; all towers have distinct
coordinates.
Output
The output is a single integer, which is the minimal required number of
different frequencies.
Sample input
4
1 1
1 20
20 1
20 20
Sample output
2
Hint
This problem does not have a polynomial-time solution, and it may require
heuristic search.