Problem C
Bob Laptop Woolmer and Eddie Desktop Barlow
Input: standard input
Output: standard output
Have you heard of Bob Woolmer, the former coach of South African cricket team? Unlike other conventional coaches, Woolmer relies on his laptop computer for storing and analyzing information on players, selecting team, planning match strategy etc. Since his laptop is his constant companion, people call him Bob Laptop Woolmer.
Having seen Woolmer in action during World Cup ’99, the BCB (Bangladesh Cricket Board) officials sacked Gordon Abacus Greenidge (he was not willing to use computers) and decided to appoint someone as charismatic as Woolmer for coaching Bangladesh cricket team. So, Eddie Barlow was appointed as the new coach. They say that he is no less than Bob Woolmer with his computer. Then why don’t you ever see him with his laptop? That is because he doesn’t have one! Actually, he has a desktop PC, and he loves his computer so much that people call him Eddie Desktop Barlow.
Now, to select Bangladesh national team for the next
World Cup, Barlow has asked BCB to
call a number of players to BKSP
camp, so that he can minutely observe them before selection. Accordingly, BCB invites around 100 players to join BKSP camp. Barlow’s strategy for
selecting the best team is as follows. He will observe each player’s batting,
bowling and fielding capabilities individually, and each player will have three
individual scores in these three aspects (batting, bowling and fielding). He
will store each player’s scores in his hard disk. After he has scored all the
players in this way, he will use his computer to select the best combination.
He believes that it is only his computer that can handle this huge data and
select the best combination to have the best capabilities in each department of
the game.
Barlow plans to have four specialist batsmen, three
specialist bowlers, three all-rounders and one wicket-keeper in the team.
Since, Khaled Mashud has no competitor for the wicket keeping position, this
position is almost fixed. Barlow is now to decide for the rest 10 positions.
For a specialist batsman, batting capability is the most important, but he
should have some fielding capability too; a specialist bowler, besides bowling,
should have some fielding and batting capabilities (since our bowlers need to
score runs in order to avoid making records(!)), and an all-rounder should have
all the capabilities. So, he sets the following rules:
For any player P
·
If
P is selected as a batsman, his
effective score = 0.8 * Batting score + 0.2 * Fielding Score
·
If
P is selected as a bowler, his
effective score = 0.7 * Bowling score + 0.10 * Batting Score + 0.2 * Fielding Score
·
If
P is selected as an all-rounder, his
effective score = 0.4 * Batting score + 0.4 * Bowling Score + 0.2 * Fielding Score
All the effective scores should be rounded to the
nearest integer for further calculation.
Barlow believes (and the mathematicians too will
believe) that the best team will have the maximum total effective score.
After the daylong practice session with the players,
Barlow is to spend his nights with writing a program that will select the best
team. He wants his program to be a bit flexible. So, it will take the number of
candidate players, number of players to be selected, that is, number of
batsmen, bowlers or all-rounders as parameters. (But the rules are fixed). But,
spending the whole night in programming, he feels tired during the next day
practice session, and cannot concentrate in his coaching or observing the
players.
So, BCB
wants to relieve Barlow from this strenuous job, and hires you to do the job
for Barlow. Now you are to write the program for selecting the best team,
according to the players’ scores assigned by Barlow. (You can write this in
your CV that you once worked with Eddie Desktop
Barlow).
Input
The input may contain several data sets.
The first line of each data set contains an integer N (10 <= N <= 100) indicating the number of players in the camp. The ith (1 <= i <= N) of the next N lines contains three integers: bti, bli and fli (0 <= bt, bl, fl <= 100) representing respectively the batting, bowling and fielding scores of the ith player. After these N lines follows another line containing three integers BT (1 <= BT <= 7), BL (0 <= BL <= 5) and AR (0 <= AR <= 4), indicating respectively the number of batsmen, bowlers and all-rounders required for the final team. You may always assume that BT + BL + AR = 10.
The input terminates with a value 0 for N.
Output
For each data set in the input, first output the team number (starting from 1). In the 2nd line print the sentence “Maximum effective score = ”, followed by the effective score of the best team. Print “Batsmen : ”, followed by the numbers of the players selected as batsmen in the 3rd line. The 4th line will contain “Bowlers : ”, followed by the numbers of the players selected as bowlers. In the 5th line print “All-rounders : ”, followed by the numbers of the players selected as all-rounders. If there are multiple solutions any one of them is acceptable. Print a blank line between the outputs of two consecutive data sets.
Sample Input
15
Sample Output
Team #1