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 $
