2008 ACM-ICPC East Central North America

ACM International Collegiate Programming Contest

2008 East Central Regional Contest

McMaster University

University of Cincinnati

University of Michigan – Ann Arbor

Youngstown State University

November 1, 2008

Sponsored by IBM

Rules:

border (or the original figure if it is the first bord er) and then the new area outlined by each border is

painted a unique color. Some examples are shown below (without the coloring of the borders ).

The example on the left shows a simple rectilinear figure (grey) with two borders drawn around it. The

one on the right is a more complicated figure; note that the border may become disconnected.

These pieces of art can get quite large, s o Bob would like a program which can draw prototypes of the

finished pieces in order to judge h ow aesthetically pleasing th ey are (and how much money they will cost

to build). To simplify things, Bob never starts with a figure that results in a border where 2 horizontal

(or vertical) sections intersect, even at a point. This disallows such cases as those shown below:

Input

Input will consist of multiple test cases. The first line of the input file will contain a single integer

Output

For each test case, output three lines: the fi rst will list the case number (as shown in the examples),

the second will contain m integers indicating the length of each border, and the third will contain m

integers indicating the additional area contributed to the artwork by each border. Both of these sets of

numbers should be listed in order, starting fr om the border nearest the original figure. Lines two and

three should be indented two spaces and labeled as shown in the examples. S ep arate test cases with a

blank line.

10 1 7

20 50 70 50 70 0 0 0 0 30

20 30 20 10 60 10 60 40 20 40

Amanda was willing to trade 1 goldfish for 3 plastic shovels. Jack realized that he could get a better

deal going through Chuck (1.8 marbles per goldfish) than by trading his marbles directly to Amanda

(2 marbles per goldfish).

Jack revels in transactions like these, but he limits the number of other people involved in a chain of

transactions to 9 (otherwise things can get a bit out of hand). Normally Jack would use a little program

he wrote to do all the necessary calculations to find the optimal deal, but he recently traded away his

computer for a fine set of ivory-handled toothpicks. So Jack needs your help.

Input

Input will consist of multiple test cases. The first line of the file will contain an integer n indicating

the number of test cases in the file. Each test case will start with a line containing two strings and

a positive integer m ≤ 50. The first string denotes the items that Jack wants, and the second string

1

item name

1

.) The values of a

1

and a

2

will be positive and ≤ 20. No person will ever need more than

2

31

Output

For each test case, output the phrase Case i: (where i is the case number starting at 1) followed by

the best possible ratio that J ack can obtain. Output the ratio using 5 significant digits, rounded. Follow

this by a single space and then the number of ways that Jack could obtain this ratio.

Sample Input

7 this 2 that

14 this 4 that

7 this 2 theother

1 theother 1 that

Sample Output

Case 1: 1.8000 1

Case 2: 0.28571 3