11804 – Argentina UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2904

Complete search.

How I did it

• I read the number of cases.
• For each case read the player and atk def points. I save each player inside a struct.
• I save the ten players into a vector.
• I sort the vector in lexicography order by name.
• To get the answer is necessary nest 5 loops and filter the atk first. If there is a tie filter by def. and if is a tie in atk and def, filter by lexicography atk order.
• Print the result.

Hints

• The input is really small so n^5 algorithm it is ok.
• The sorting is first by atk, if there is two equals atks, sort by def if there is a tie, sort the atk player by name.

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

using namespace std;

struct pepe
{
    string name;
    int atk;
    int def;
};

vector<pepe> vec, atkAns,defAns;

bool cmp(pepe a, pepe b)
{
    return a.name < b.name;
}

int getDef(int a,int b,int c,int d,int e)
{
    map<int,int> pMap;
    pMap[a] = 1;pMap[b] = 1;pMap[c] = 1;
    pMap[d] = 1;pMap[e] = 1;

    int ans = 0;
    for(int i=0; i<10; i++)
    {
        if(pMap[i] == 0)
          ans += vec[i].def;
    }
return ans;
}

void setAns(int a,int b,int c,int d,int e)
{
    map<int,int> pMap;
    pMap[a] = 1;pMap[b] = 1;pMap[c] = 1;
    pMap[d] = 1;pMap[e] = 1;

    atkAns.clear(), defAns.clear();

    for(int i=0; i<10; i++)
    {
        if(pMap[i] == 1)
          atkAns.push_back(vec[i]);
        else
            defAns.push_back(vec[i]);
    }
}
void checkOrder(int a,int b,int c,int d,int e)
{
    vector<pepe> tmp;
    tmp.push_back(vec[a]);tmp.push_back(vec[b]);tmp.push_back(vec[c]);
    tmp.push_back(vec[d]);tmp.push_back(vec[e]);
    bool flag = false;

    for(int i=0; i<atkAns.size(); i++)
    {
        if(tmp[i].name < atkAns[i].name)
        {
            flag = true;
            break;
        }
        else if(tmp[i].name > atkAns[i].name)
                break;
    }
    if(flag)
       setAns(a,b,c,d,e);
}
int main()
{
    string name;
    pepe p;
    int casos, atk, def;
    int vAtk, vDef, tmp, tmpDef;

    scanf("%d", &casos);
    for(int z=1; z<=casos; z++)
    {
            for(int i=1; i<=10; i++)
            {
                cin>>p.name;
                scanf("%d %d", &p.atk, &p.def);
                vec.push_back(p);
            }
            sort(vec.begin(), vec.end(), cmp);

            vAtk = vDef = -1000;

            for(int a=0; a<vec.size(); a++)
                for(int b=a+1; b<vec.size(); b++)
                   for(int c=b+1; c<vec.size(); c++)
                       for(int d=c+1; d<vec.size(); d++)
                           for(int e=d+1; e<vec.size(); e++)
                           {
                                tmp = vec[a].atk + vec[b].atk + vec[c].atk + vec[d].atk + vec[e].atk;
                                if(tmp > vAtk)
                                {
                                    vAtk = tmp;
                                    vDef = getDef(a,b,c,d,e);
                                    setAns(a,b,c,d,e);
                                }
                                else if(tmp == vAtk)
                                {
                                    tmpDef = getDef(a,b,c,d,e);
                                    if(tmpDef > vDef)
                                    {
                                        vAtk = tmp;
                                        vDef = tmpDef;
                                        setAns(a,b,c,d,e);
                                    }
                                    else if(tmpDef == vDef)
                                    {
                                        checkOrder(a,b,c,d,e);
                                    }
                                }
                           }
            printf("Case %d:\n", z);
            for(int i=0; i<atkAns.size(); i++)
            {
                if(i==0)
                  printf("(%s, ", atkAns[i].name.c_str());
                else if(i == atkAns.size() - 1)
                       printf("%s)\n", atkAns[i].name.c_str());
                else
                    printf("%s, ", atkAns[i].name.c_str());
            }

            for(int i=0; i<defAns.size(); i++)
            {
                if(i==0)
                  printf("(%s, ", defAns[i].name.c_str());
                else if(i == defAns.size() - 1)
                       printf("%s)\n", defAns[i].name.c_str());
                else
                    printf("%s, ", defAns[i].name.c_str());
            }
            vec.clear(), atkAns.clear(),defAns.clear();
    }
return 0;
}