PDA

View Full Version : Here's a trivia question for all of you smart programmers



Trivia_Question
01-10-2003, 01:23 PM
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 $

Govtcheez
01-10-2003, 01:31 PM
And seeing it's posted from a school, I remember another, less wordy trivia question...

"How many message board programmers does it take to do my homework?"

PJYelton
01-10-2003, 01:32 PM
LOL I think its funny that he calls us smart programmers and then proceeds to think we are stupid enough to do his homework for him!

drat you beat me cheese!

Trivia_Question
01-10-2003, 01:37 PM
Originally posted by PJYelton
LOL I think its funny that he calls us smart programmers and then proceeds to think we are stupid enough to do his homework for him!

drat you beat me cheese!

It's not homework, I want to see if anyone can get this.

Yes, Salem, you're right, and this question is the hardest of them all.

MethodMan
01-10-2003, 01:37 PM
Originally posted by Govtcheez

"How many message board programmers does it take to do my homework?"

LMAO

I dont know if its funnier when people bluntly say, can you do my Homework for me, or when they try to disguise it like this.

MethodMan
01-10-2003, 01:39 PM
Originally posted by Trivia_Question
It's not homework, I want to see if anyone can get this.

Yes, Salem, you're right, and this question is the hardest of them all.

So if someone does get it, I would assume you would like to see the code on how it is done?

itld
01-12-2003, 10:03 PM
howdy,
i swear i saw this exact question posted on cpp-home.com.

M.R.

adrianxw
01-12-2003, 11:10 PM
Look through the link in this thread. You'll find this and many other problems...

http://cboard.cprogramming.com/showthread.php?s=&threadid=32146