73 - ZOJ Monthly, December 2008 - D
ZJU ICPC Summer Camp 2008 is going to end shortly, and 18 members will be selected to form the ZJU ICPC teams, which will participate in the regionals this year. However, team forming is usually a headache for the coaches, since in order to get the best achievement, the members should be selected carefully so the abilities of the teams are maximized. This is a diffcult task, as it is hard to define what the ability of a team is, and the coaches could only make a forming plan that is intuitively good in the past. This year they've found a new method to measure the abilities of the team members: radar charts. For example, if we just consider six aspects of a member's abilites: Greedy, DP, Math, Geometry, Graph and Others, and compute the relative value of each aspect with the performance in summer camp (once the problems are classilied, this is an easy job). Then we can get a chart like this picture:
To make things simpler, we believe that in each aspect, the ability of a team is the maximum ability of three members, and define the area of the resulting diagram to be the overall ability of this team. Then it is very easy to write a program to find the best team forming plan to achieve the maximum abilities for all teams. But as you may already know, the coaches are too lazy to write programs, so it's your turn to write a program to prove your skill now. But note that in order to get a high rank in the world finals, there should always be one or two teams whose abilites are as good as possible. So your program should first form one team with the best overall ability or two teams with the highest total abilites, then form the remaining teams to get the maximum total abilities.
Each case begins with three positive integers A, N and F, where A is the number of aspects to be considered (3 <= A <= 20), N is the number of ICPC team members (N <= 18, and N is a multiple of 3) and F is either 1 or 2 (F <= N / 3), means the first F team(s) should be the best one(s). Then N lines followed, each describes a member with his/her name and relative abilities in the A aspects. The names of members are distinct and each contains up to 31 characters that is either a letter or an underscore ('_'). The values of relative abilites are between 0 and 100, inclusive, with no more than two digits after the decimal points.The radar charts are drawn in the same order as the input (the Ath aspect is next to the first one, of course).
There's a blank line between every two successive cases. Processing to the end of file.
For each test case, print N / 3 lines each represents a team with the names of three members. Any solution that first maximize the total abilites of the first F team(s) and then maximize the total abilites of remaining teams will be accepted.
6 6 1 sghao126 90.33 57.13 86.78 84.88 83.79 90.78 lyt 76.66 82.56 78.52 55.49 31.02 45.37 gy 71.71 81.2 79.84 82.65 69.16 74.89 liux0229 74.16 61.03 81.33 73.39 85.01 80.7 Charizard 94.32 86.96 87.51 76.02 77.25 77.38 hhanger 93.37 78.93 76.47 84.88 75.79 77.38
sghao126 liux0229 Charizard lyt gy hhanger
The picture in this description and the data used in sample are retrieved from http://iadjust3.scm.ca/tcstats/.
Author: XIAO, Dong
Source: ZOJ Monthly, December 2008