12673 Football 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=4411

Greedy and data structures.

How I did it

• I read the number of matches and goals.
• I read the team goals and received goals.
• If my team win the match increment 1 to a win counter.
• If the match it is a tie, increment 1 to a tie counter.
• If my team lose the match, save the pair into a vector.
• After reading the data, I sort the lose match vector.( Where abs(teamGoals – receivedGoas) is smaller).
• For each win. points = win * 3;
• For each tie decrease the goals and increment 3 in the points(if I have enough goals). Add 1 point for the rest of ties.
• Traverse the lose vector and  if the goals are greater or equal than the diference of the current array position, increment the points(tie or win).
• Print the points.

Hints

•  The aproach for this problem is greedy, complete search or backtracking will be TLE.
• Only we need to save the lose games.

Code

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;

bool cmp(pair<int,int> a, pair<int,int> b)
{
 int v1 = abs(a.first - a.second);
 int v2 = abs(b.first - b.second);

 return v1 < v2;
}

int main()
{
int matches, goals, win, draw, tot, m, v, needGoals;
while(scanf("%d %d", &matches, &goals) == 2)
{
    win = draw = tot = 0;
    vector<pair<int,int> > vec;
    for(int i=0; i<matches; i++)
    {
        scanf("%d %d", &m, &v);
        if(m == v)
           draw++;
        else if(m>v)
             win++;
        else
        {
            pair<int,int> p = make_pair(m, v);
            vec.push_back(p);
        }
    }

    sort(vec.begin(), vec.end(), cmp);

    tot = win*3;
    if(draw == goals)
    {
        tot = tot + (draw * 3);
        goals = 0;
    }
    else if(draw > goals)
    {
        tot =  tot + (goals * 3);
        draw = draw - goals;
        tot = tot + draw;
        goals = 0;
    }
    else
    {
        tot = tot + (draw * 3);
        goals = goals - draw;
    }

    for(int i=0; i<vec.size(); i++)
    {
        needGoals = abs(vec[i].first - vec[i].second) + 1;
        if(goals >= needGoals)
        {
            tot+=3;
            goals -= needGoals;
        }
        else if(goals == needGoals - 1)
        {
            tot++;
            goals -= needGoals - 1;
        }
        else
            break;
    }
    printf("%d\n", tot);
}
return 0;
}