ICPC 2006 · Problem F · Building a Clock

Input File: clock.in

In Old Town Square in the city of Prague, there is a beautiful Astronomical Clock, constructed in the year 1410. For centuries, the clockmaker’s art consisted of using gears to connect a shaft, turning at a known rate, to other shafts until, by the proper combination of gears, two shafts could be made to turn at the correct rates to represent minutes and hours.

You must write a program that, given an input shaft speed and a collection of gears, computes how the gears can be connected to create a clock with an hour hand and a minute hand. You may use as many shafts as you like, but each shaft may have a maximum of t gears. All the gears on a shaft turn at the same rate. If a gear having T1 teeth turning at a rate R1 is engaged with another gear having T2 teeth, the turning rate of the second gear is –R1(T1/T2). Your solution must include two shafts, a minute shaft that turns clockw at the rate of one revolution per hour, and an hour shaft that turns clockwise at the rate of one revolution per twelve hours. Your solution is not required to use all the available g

In

The inpu (3 ≤ N ≤ 6), the number of gears available for building a clock. N is followed by another integer R (-3600 ≤ R ≤ 3600, R ≠ 0), the turning rate of the input shaft, which is the number of revolutions m in 24 hours. (A positive number represents clockwise rotation, and a negative number represents counter-clockwise rotation.) R is followed by N gear descriptions. Each gear description is a pair: a one-character name that identifies the gear, followed by an integer T (6 ≤ T ≤ 120), that is the number of teeth on the gear. The names and numbers on each input line are separated by spaces, as shown in the sample input.

T

O

For each tri clock using the given set of gears, the line containing the trial number must be followed by two more output lines, one for the minute hand and one for the hour hand. Otherwise, the line containing the trial number must end with th words IS IMPOSSIBLE as shown in the sample output.

e for the minute hand T by a sequence of gears to the minute shaft. The plan consists of a sequence of shafts, separated by hyphens. Each shaft is represented by one or two characters. The first character is the name of the driven gear–the gear on the shaft that is engaged with a gear on the previous shaft. For the input shaft, use an asterisk (*) to represent the absence of a driven gear. The second character describing a shaft is the name of the driving gear–the gear on shaft that is engaged with a gear on the next shaft. The driven gear and the driving gear can be the same gear, in which case the shaft is described by a single character which is the name of this gear. The last shaft in the plan is minute shaft, described by a single letter which is the name of its driven gear.

T Each gear may occur only once in the clock. The minute plan and the hour plan may have an initial part in common, owever. A gear in a common initial part will occur both in the minute plan and the hour plan. For the same reason,

s the

nt valid output lines:

t having one gear, engaged with an intermediate shaft having two gears, engaged with an hour shaft having one gear.

ermediate shaft having one ear, engaged with a minute shaft having one gear.

ut shaft is turning at the orrect rate for the minute shaft.

If there are multiple ways to build a clock using the given gears, print the solution that uses the minimum number of afts. In case of a tie for the minimum number of shafts, print the solution that uses the minimum number of gears.

Output for the Sample Input

R 50 A 40 B 30 C 14
R 45 A 40 B 30 C 14
                                     *B-A-RP-C-Q

h a given shaft can be used in both the hour plan and the minute plan. If a shaft is used in both plans, it may or may not have the same description in both plans. For example, a shaft containing a single gear named A will be represented as A in both plans. On the other hand, a shaft containing three gears named A, B, and C might be represented as AB in the minute plan (if B is the driving gear in that plan) and as AC in the hour plan (if C i driving gear in that plan).

The following lines represe

Hours:   *A-BC-D

An input shaf

An input shaft having one gear, engaged with an int

Minutes: *A-B-C

g

A plan in which no gears are needed because the inp

Minutes: *

c

sh In case of a tie for both the minimum numbers of shafts and gears, print the solution whose string description is alphabetically first. The string description of a solution is its minute plan, followed by its hour plan, concatenated together with asterisks and hyphens removed. For example, a solution in which the minute plan is *A-B and the hour plan is *A-BC-D-E has the string description ABABCDE.

Print one blank line between trials.

Sample Input

Trial 1
6 40 P 7 Q 84
Minutes: *B-A-R
6 40 P 7 Q 84
Hours:
0
Trial 2 IS IMPOSSIBLE