Here's a trivia question for all of you smart programmers

Matching Warriors

-------- --------

The Kingdom of Irfrissable Polytudinous Warriors (KIPW)

has a tournament every year between its two tribes, the

Kay (K), and the Kaykay (KK). This consists of contests

between individual warriors, each tribe having the same

number, and the tribe with the most winning warriors

wins the coveted thud cup.

Its up to the tribe that lost last year (currently the

K) to choose which warriors will fight each other. The

K are using science to do this, and have derived the

following method of determining the probability that

warrior i will defeat warrior j. To this end the K have

assigned scores for 6 skills to each warrior, so the

scores for warrior i are s[i][k] for k = 0,1,2,3,4,5.

Then the probability of warrior i defeating warrior j

is

I / (I + J)

where

I = max{I',0}

I' = max{ s[i][k] - s[j][k] : k=0,1,2,3,4,5 }

J = max{J',0}

J' = max{ s[j][k] - s[i][k] : k=0,1,2,3,4,5 }

and in the special case that I = J = 0, the probability

is 0.5.

It is your task to compute for K the matching of

warriors that will give K the greatest expected number

of victories.

Input

-----

For each of several data sets:

Line 1: The number n of warriors in each tribe,

0 < n <= 20;

Lines 2 .. 1+n:

One line for each warrior of K, where the

warriors are numbered 1 .. n in increasing

order, and the line for warrior i contains:

s[i][0] s[i][1] ... s[i][5]

0 <= s[i][k] <= 10 for every i and k.

The s[i][k] are all integers.

Lines 2+n .. 1+2n:

Ditto for the warriors of KK.

The input ends with a line containing a single 0.

Output

------

One line per instance containing `Instance #:' followed

by the KK warrior numbers matched to the warriors of

tribe K in increasing order of the K warrior numbers.

E.g., `2 3 1' means K warrior 1 fights KK warrior 2,

K warrior 2 fights KK 3, K 3 fights KK 1.

Sample Input

------ -----

2

1 0 0 0 0 0

0 2 0 0 0 0

0 0 1 0 0 0

0 0 0 3 0 0

3

1 0 0 0 0 0

0 2 0 0 0 0

0 0 3 0 0 0

0 0 2 0 0 0

0 1 0 0 0 0

3 0 0 0 0 0

0

Sample Output

------ ------

Instance 1: 2 1

Instance 2: 3 2 1

te: 2001/10/11 19:34:13 $

$RCSfile: warriors.txt,v $

$Revision: 1.5 $