PROB3: MATCH

Be a match maker.

DESCRIPTION

The dating service MatchMaker.com has a list of men and a list of women. The number of men is equal to the number of women. In addition to their names, MatchMaker.com keeps track of two attributes about each of their clients: the person's IQ (intelligence quotient) and the person's height. MatchMaker.com wishes to match each man with a woman in an optimal way, so that the deviations of the two attributes in the resulting man / woman pairs are minimized.

INPUT: prob3.dat

The input file will consist of one or more data sets of the form


N
WOMAN_NAME(1) WOMAN_IQ(1) WOMAN_HEIGHT(1)
WOMAN_NAME(2) WOMAN_IQ(2) WOMAN_HEIGHT(2)
.
.
.
WOMAN_NAME(N) WOMAN_IQ(N) WOMAN_HEIGHT(N)
MAN_NAME(1) MAN_IQ(1) MAN_HEIGHT(1)
MAN_NAME(2) MAN_IQ(2) MAN_HEIGHT(2)
.
.
.
MAN_NAME(N) MAN_IQ(N) MAN_HEIGHT(N)


N will be a positive integer not larger than 13. The NAME of men and women will consist of no more than 11 lower case alphanumeric characters (a-z, 0-9). The IQ will be an integer in the range 10..199. The HEIGHT will be an integer in the range 145..189. One or more blank spaces will separate the NAME, IQ and HEIGHT values, but there will be no leading or trailing white space.

Here is an example of an input file:

       column   11111111112
       12345678901234567890
line 1:7[EOL]
     2:mindy    70 145[EOL]
     3:jennifer 80 155[EOL]
     4:kathy    90 165[EOL]
     5:allison 100 175[EOL]
     6:alice   105  156[EOL]
     7:jenna   110  158[EOL]
     8:mary    115  160[EOL]
     9:john   110   175[EOL]
    10:jack   85    170[EOL]
    11:steve  115   170[EOL]
    12:bill   105   149[EOL]
    13:bob     80   155[EOL]
    14:thomas  75   179[EOL]
    15:mike   120   168[EOL]
    16:3[EOL]
    17:mindy 100   180[EOL]
    18:jenny 120   155[EOL]
    19:kathy 105   168[EOL]
    20:jack 104    169[EOL]
    21:bob  119    156[EOL]
    22:bill  99    179[EOL]
      :[EOF]

OUTPUT: prob3.out

For each N man-woman pairs in the input data set, there will be N+2 lines of output in the format:


N
WOMAN_PAIR_NAME(1) MAN_PAIR_NAME(1) PAIR_DEVIATION(1)
WOMAN_PAIR_NAME(2) MAN_PAIR_NAME(2) PAIR_DEVIATION(2)
.
.
.
WOMAN_PAIR_NAME(N) MAN_PAIR_NAME(N) PAIR_DEVIATION(N)
TOTAL_DEVIATION


Each woman-man pair name is separated by exactly one blank space. The PAIR_DEVIATION is defined as the absolute value of the difference in IQ, plus the absolute value of the difference in height of the pair.

The TOTAL_DEVIATION is the sum of the PAIR_DEVIATION. The crucial constraint on the output is that the pairing should minimize the TOTAL_DEVIATION compared to all possible man-woman pairings. Note that there may be more than one such minimal configuration.

One of several possible correct outputs corresponding to the example input would be:

       column   111111111122222222223
       123456789012345678901234567890
line 1:Program 3 by team 0[EOL]
     2:7[EOL]
     3:mindy thomas 39[EOL]
     4:jenna mike 20[EOL]
     5:allison john 10[EOL]
     6:kathy jack 10[EOL]
     7:mary steve 10[EOL]
     8:alice bill 7[EOL]
     9:jennifer bob 0[EOL]
    10:96[EOL]
    11:3[EOL]
    12:jenny bob 2[EOL]
    13:kathy jack 2[EOL]
    14:mindy bill 2[EOL]
    15:6[EOL]
    16:End of program 3 by team 0[EOL]
      :[EOF]