[UVA] 11804 - Argentina
A |
Argentina |
The Argentine football team coach, the great Diego Maradona, is going to try out a new formation this year. Formation describes how the players are positioned on the pitch. Instead of the conventional 4-4-2 or 4-3-3, he has opted for 5-5. This means there are 5 attackers and 5 defenders.
You have been hired by Argentina Football Federation (AFF) to write a code that will help them figure out which players should take the attacking/defensive positions.
Maradona has given you a list containing the names of the 10 players who will take the field. The attacking ability and the defensive ability of each player are also given. Your job is to figure out which 5 players should take the attacking positions and which 5 should take the defensive positions.
The rules that need to be followed to make the decision are:
- The sum of the attacking abilities of the 5 attackers needs to be maximized
- If there is more than one combination, maximize the sum of the defending abilities of the 5 defenders
- If there is still more than one combination, pick the attackers that come lexicographically earliest.
Input
The first line of input contains an integer T(T<50) that indicates the number of test cases. Each case contains exactly 10 lines. The ith line contains the name of the ith player followed by the attacking and defending ability of that player respectively. The length of a player’s name is at most 20 and consists of lowercase letters only. The attacking/defending abilities are integers in the range [0, 99].
Output
The output of each case contains three lines. The first line is the case number starting from 1. The next line contains the name of the 5 attackers in the format (A1, A2, A3, A4, A5) where Ai is the name of an attacker. The next line contains the name of the 5 defenders in the same format. The attackers and defenders names should be printed in lexicographically ascending order. Look at the sample for more details.
Sample Input |
Sample Output |
1 sameezahur 20 21 sohelh 18 9 jaan 17 86 sidky 16 36 shamim 16 18 shadowcoder 12 9 muntasir 13 4 brokenarrow 16 16 emotionalblind 16 12 tanaeem 20 97 |
Case 1: (emotionalblind, jaan, sameezahur, sohelh, tanaeem) (brokenarrow, muntasir, shadowcoder, shamim, sidky) |
Problemsetter: Sohel Hafiz, Special Thanks: Shamim Hafiz, Jane Alam jan
先排序,之後就不用考慮名字的字典順序問題,按照字典順序窮舉就行了
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
struct p {
string name;
int a, b;
};
p P[10];
int at, def;
bool cmp(p a, p b) {
int i;
for(i = 0; i < a.name.length() && i < b.name.length(); i++)
if(a.name[i] > b.name[i])
return 0;
else if(a.name[i] < b.name[i])
return 1;
return a.name.length() < b.name.length();
}
int A[10], B[10];
int aA[10], aB[10];
void dfs(int idx, int a, int d, int ta, int td) {
if(idx == 10) {
if(ta > at || (ta == at && td > def)) {
at = ta, def = td;
int i;
for(i = 0; i < 5; i++)
aA[i] = A[i], aB[i] = B[i];
}
return;
}
if(a != 5) {
A[a] = idx;
dfs(idx+1, a+1, d, ta+P[idx].a, td);
}
if(d != 5) {
B[d] = idx;
dfs(idx+1, a, d+1, ta, td+P[idx].b);
}
}
int main() {
int t, cases = 0, i;
scanf("%d", &t);
while(t--) {
for(i = 0; i < 10; i++)
cin >> P[i].name >> P[i].a >> P[i].b;
sort(P, P+10, cmp);
at = 0, def = 0;
dfs(0, 0, 0, 0, 0);
printf("Case %d:\n", ++cases);
printf("(");
for(i = 0; i < 5; i++) {
if(i) printf(", ");
cout << P[aA[i]].name;
}
printf(")\n");
printf("(");
for(i = 0; i < 5; i++) {
if(i) printf(", ");
cout << P[aB[i]].name;
}
printf(")\n");
}
return 0;
}