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;
}

696 – How Many Knights 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=637

Brute force.

How I did it

• I read the number of rows and columns.
• If rows = 1 or columns = 1 I return row * columns.
• If the rows = 2 or columns = 2 I simulate the process. The recurrence for this case is:

KK..KK..kk..kk
KK..KK..kk..kk

• Otherwise I simulate the process. The recurrence for any other case is:

K.K.K
.K.K.
K.K.K
.K.K.

• Print the number of knights.

Hints

• Solve the problem in paper.
• This solution is slow, you can solve this problem with a direct formula too.

Code

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int getAns(int r, int c)
{
    int val, ans = 0;
    if(r == 1 || c == 1)
       return r * c;
    else if (r == 2 || c == 2)
    {
        if(c == 2)
           swap(r, c);
        int cont = 0;
        for(int i=1; i<=c; i++)
        {
            cont++;
            if(cont <= 2)
                ans++;
            else if(cont == 4)
                cont = 0;
        }

    return ans * 2;
    }

    ans = 0;
    for(int i=1; i<=r; i++)
    {
        for(int j=1; j<=c; j++)
        {
            if(i % 2 != 0)
            {
                if(j % 2 != 0)
                {
                    ans++;
                }
            }
            else
            {
                if(j % 2 == 0)
                  ans++;
            }
        }
    }
    return ans;
}

int main()
{
    int row, col, ans;

    while(scanf("%d %d", &row, &col))
    {
        if(!row && !col)
           break;

        ans = getAns(row, col);
        printf("%d knights may be placed on a %d row %d column board.\n", ans, row, col);
    }
return 0;
}

11503 – Virtual Friends 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=2498

Union Find disjoint sets.

How I did it

• I read the number of cases.
• For each case I read the number of friendships to read.
• For each name I check if the name exist in a map. If a name is not in the map I added to the map.
• I call union_set.
• Print the size of the set with the name of one person in the new friendship.

Hints

•  For each friendship you need to print one line with the size of the set. i.e (3 4 print ans, 3 4 print ans again).
• The answer is just union find.

Code

#include <iostream>
#include <cstdio>
#include <map>
#define  ELEMENTS  100002

using namespace std;

map<string,int> myMap;
int index;

int parent[ELEMENTS];
int rank[ELEMENTS];
int numDisjointSets;

void make_sets(int number_of_elements)
{
    numDisjointSets = number_of_elements;
    int i;
    for(i = 0; i < number_of_elements; i++)
    {
        parent[i] = i;
        rank[i] = 1;
    }
}

int find_set(int element)
{
    if(element != parent[element])
        parent[element] = find_set(parent[element]);
    return parent[element];
}

bool isSameSet(int i, int j)
{
    return find_set(i) == find_set(j);
}

void set_union(int x, int y)//where x and y are elements of different sets
{
    int rx, ry; //roots or representatives of x and y sets
    rx = find_set(x);
    ry = find_set(y);
    if(rx == ry) // it means the elements already are in the same set
        return;

    numDisjointSets--;
    if(rank[rx] > rank[ry])
    {
        rank[rx] += rank[ry];
        parent[ry] = rx;
    }
    else
    {
        rank[ry] += rank[rx];
        parent[rx] = ry;
    }
}

int getNumSets()
{
    return numDisjointSets;
}

int sizeOfSet(int i)
{
    return rank[find_set(i)];
}

void setIndex(string str)
{
    if(myMap.find(str) == myMap.end())
       myMap[str] = index++;
}

int main()
{
    string name1, name2;
    int casos, friendship;

    scanf("%d", &casos);
    while(casos--)
    {
        index = 0;
        scanf("%d", &friendship);
        make_sets(ELEMENTS);
        myMap.clear();

        for(int x=0; x<friendship; x++)
        {
            cin>>name1>>name2;
            setIndex(name1);
            setIndex(name2);

            set_union(myMap[name1], myMap[name2]);

            int answer = sizeOfSet(myMap[name1]);
            printf("%d\n", answer);
        }
    }
return 0;
}

10684 – The jackpot 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=1625

Dynamic Programming, 1D range sum, Kanade Algorithm.

How I did it

• I read the data in a vector.
• Init ans = tot = 0. Ans will save the answer, tot will save the cumulative value of the range.
• Traverse the vector. If I found a negative cumulative value set tot = 0. Otherwise increment the range.
• If ans is less than 0 print losing streak, otherwise I print ans.

Hints

•  It is a clasic DP problem. Standard Kanade Algorithm.
• 0 is a valid answer.

Code

#include <cstdio>
#include <algorithm>

using namespace std;

int vec[10010];

int main()
{
    int ele, ans, tot;

    while(scanf("%d", &ele))
    {
        if(!ele)
           break;

        for(int x=0; x<ele; x++)
            scanf("%d", &vec[x]);

        ans = tot = 0;

        for(int x=0; x<ele; x++)
        {
            tot += vec[x];
            ans = max(tot, ans);

            if(tot < 0)
              tot = 0;
        }

        if(ans > 0)
           printf("The maximum winning streak is %d.\n", ans);
        else
            printf("Losing streak.\n");
    }
return 0;
}

247 – Calling Circles 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=183

Graphs, Strongly Connected Components.

How I did it

• I read the number of nodes and edges.
• Read the data of the graph.
• I parse the strings and set a map<string,int> with the indices of the nodes(0 to nodes – 1).
• I save the graph as an Adjacency list.
• Traverse all nodes and for each unvisited node call Tarjan Algorithm.
• En every tarjan call I find the nodes that belong to the current SCC, and print the elements in that subset (map<string,int>).

Hints

•  The key is parse the strings and assign a name for each person.
• The input is really small.
• I print a blank line between the cases.(The last case does not need the blank line).

Code

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#define  DFS_BLACK 1
#define  DFS_WHITE -1

using namespace std;
typedef vector<int> vi;

vector<vi> graph;
vi dfs_num, dfs_low, S, visited;
int dfsNumberCounter, numSCC;
set<string> mySet;
map<string,int> myMap;
map<int, string> nameMap;

void init(int nodes)
{
    graph.clear();
    graph.resize(nodes);
    dfs_num.resize(nodes);
    fill(dfs_num.begin(), dfs_num.end(), DFS_WHITE);
    dfs_low.resize(nodes);
    fill(dfs_low.begin(), dfs_low.end(), 0);
    visited.resize(nodes);
    fill(visited.begin(), visited.end(), 0);
}

void readGraph(int edges)
{
    myMap.clear();
    mySet.clear();
    int index = 0;

    string str1, str2;
    int node1, node2;

    for(int x=0; x<edges; x++)
    {
        cin>> str1 >> str2;

        if(mySet.find(str1) == mySet.end())
        {
            myMap[str1] = index;
            nameMap[index] = str1;
            mySet.insert(str1);
            index++;
        }
        if(mySet.find(str2) == mySet.end())
        {
            myMap[str2] = index;
            nameMap[index] = str2;
            mySet.insert(str2);
            index++;
        }
        node1 = myMap[str1];
        node2 = myMap[str2];
        graph[node1].push_back(node2);
    }
}

void tarjanSCC(int node)
{
    dfs_low[node] = dfs_num[node] = dfsNumberCounter++;
    S.push_back(node);
    visited[node] = 1;

    for(int x=0; x<graph[node].size(); x++)
    {
        if(dfs_num[graph[node][x]] == DFS_WHITE)
          tarjanSCC(graph[node][x]);
        if(visited[graph[node][x]])
            dfs_low[node] = min(dfs_low[node], dfs_low[graph[node][x]]);
    }

    if(dfs_low[node] == dfs_num[node])//This is the root
    {
        ++numSCC;
        while(1)
        {
            int v = S.back();
            S.pop_back();

            visited[v] = 0;

            if(node == v)
            {
                printf("%s\n", nameMap[v].c_str());
                break;
            }
            else
                printf("%s, ", nameMap[v].c_str());
        }
    }
}

int main()
{
    string str;
    int nodes, edges, casos = 1;
    bool flag = false;
    while(scanf("%d %d", &nodes, &edges))
    {
        if(!nodes && !edges)
           break;

        init(nodes);
        readGraph(edges);

        dfsNumberCounter = numSCC = 0;
        if(!flag)
           flag = true;
        else
            printf("\n");
        printf("Calling circles for data set %d:\n", casos++);
        for(int i=0; i<graph.size(); i++)
        {
            if(dfs_num[i] == DFS_WHITE)
               tarjanSCC(i);
        }
    }
return 0;
}

10763 – Foreign Exchange 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=1704

Data structures, STL MAP.

How I did it

• I read the pair numbers to read until I find a 0.
• I read all the pairs and save this into a map<int,int>.
• I traverse the map and check if the inverted key and value is equal to the key value. If this values are diferents I break the loop and set the answer as NO.Otherwise set the answer as YES.
• Print the answer.

Hints

•  The input is big 500000. So carefull if you want to use another brute force approach.

Code

#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;

int main()
{
    map< pair<int,int>, int> myMap;
    int tot, from, to;
    pair<int,int> tmp;
    while(scanf("%d", &tot))
    {
        if(!tot)
           break;

        myMap.clear();

        for(int i=0; i<tot; i++)
        {
            scanf("%d %d", &from, &to);
            pair<int,int> p = make_pair(from, to);
            myMap[p]++;
        }

        bool flag = true;
        for(map< pair<int,int>, int>::iterator it=myMap.begin(); it!=myMap.end(); it++)
        {
            tmp = it->first;
            swap(tmp.first, tmp.second);
            if(myMap[tmp] != myMap[it->first])
            {
                flag = false;
                break;
            }
        }

        if(flag)
           printf("YES\n");
        else
            printf("NO\n");
    }
}

10686 – SQF Problems 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=1627

Data structures, STL map, STL set.

How I did it

• I read the number cases.
• For each case I read the number of categories.
• I read the category name, the words and the needed words. I save this in a map “key= category name, value= number of words and the needed words.
• I read the words for the category and I save this in another map “key=category name” value= the words. (Here carefull saving the same word two or three time, for that im using a set).
• I read the other lines and save the words into a set.
• I traverse the words  of the last line and check every category. Compare the quantity with the first map.
• Print the answer.

Hints

•  If the problem fits in more than one category, you shoud print them all, in the order they appear in the input, separated only by commas.
• The end of a problem description is indicated by a blank line.
• Just keep the category problem as a key in every map.

Input

3
2
Graph 4 3
node
edge
directed
distance
Geometrical 4 2
point
convex
polygon
boring
This is neither a SQF problem nor a graph problem.
This is a boring geometrical problem. In this problem
you should calculate the convex area of a regular polygon.

2
Graph 4 3
node
edge
directed
distance
Geometrical 4 2
point
convex
polygon
boring
This is neither a SQF problem nor a graph problem node, edge directed.
This is a boring geometrical problem. In this problem
you should calculate the convex area of a regular polygon.

2
Graph 4 3
node
edge
directed
distance
Geometrical 4 2
point
convex
polygon
boring
This is neither a SQF problem nor a graph problem.
This is a boringa geometrical problem. In this problem
you should calculate the convexaaa area of a regular polygodsn.

Output

Geometrical
Graph,Geometrical
SQF Problem

Code

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

using namespace std;

map<string, pair<int,int> > catMap;
map<string, set<string> >  myMap;
vector<string> vec;
vector<string> ansVec;
set<string> mySet;

void init()
{
    catMap.clear();
    myMap.clear();
    vec.clear();
    ansVec.clear();
    mySet.clear();
}

void getWords(string str)
{
    string word = "";
    for(int x=0; x<str.size(); x++)
    {
        if(isalpha(str[x]))
           word += str[x];
        else if(word.size() != 0)
        {
            mySet.insert(word);
            word = "";
        }
    }
    if(word.size() != 0)
       mySet.insert(word);
}

void getAns()
{
    string tmp;
    int cont;
    for(int x=0; x<vec.size(); x++)
    {
        tmp = vec[x];
        set<string> cSet = myMap[tmp];
        cont = 0;

        for(set<string>::iterator it = mySet.begin(); it!=mySet.end(); it++)
        {
            if(cSet.find(*it) != cSet.end())
               cont++;
        }

        if(cont >= catMap[tmp].second)
           ansVec.push_back(tmp);
    }
}

int main()
{
    int casos, categorias, words, needed;
    string catName, str;

    scanf("%d", &casos);

    while(casos--)
    {
        init();
        scanf("%d", &categorias);
        for(int i=0; i<categorias; i++)
        {
            cin>>catName;
            vec.push_back(catName);
            scanf("%d %d", &words, &needed);
            pair<int,int> p = make_pair(words, needed);
            catMap[catName] = p;

            for(int j=0; j<words; j++)
            {
                cin>>str;
                myMap[catName].insert(str);
            }
        }
        getline(cin, str);//trash
        while(getline(cin, str))
        {
            if(str.size() == 0)
               break;
            getWords(str);
        }
        getAns();

        if(ansVec.size() == 0)
           printf("SQF Problem.\n");
        else
        {
            for(int g=0; g<ansVec.size() - 1; g++)
            {
                cout<<ansVec[g]<<',';
            }
            cout<<ansVec[ansVec.size() - 1]<<'\n';
        }
    }
return 0;
}

11360 – Have Fun with Matrices 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=2345

Data structures, 2D array manipulation.

How I did it

• I read the number cases.
• I read the size of the matrix. (Because the size is n * n).
• I read the matrix.
• I read the number of operations.
• I read the operation and execute it.
• I print the matrix.

Hints

•  It’s really easy to put every operation into a function.
• Print a blank line after every case.

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#define  NODES 11

using namespace std;

int matriz[NODES][NODES];
int tmpMatriz[NODES][NODES];

void readMatrix(int tam)
{

    string tmp, data = "";

    for(int x=0; x<tam; x++)
    {
        cin>>tmp;
        data += tmp;
    }

    int index = 0;
    for(int x=0; x<tam; x++)
        for(int y=0; y<tam; y++)
            matriz[x][y] = data[index++] - '0';
}

void print(int tam)
{
    for(int x=0; x<tam; x++)
    {
        for(int y=0; y<tam; y++)
            printf("%d",matriz[x][y]);
        printf("\n");
    }
    printf("\n");
}

void addOne(int tam)
{
    for(int x=0; x<tam; x++)
        for(int y=0; y<tam; y++)
        {
            matriz[x][y]++;
            if(matriz[x][y] > 9)
               matriz[x][y] = 0;
        }
}

void restOne(int tam)
{
    for(int x=0; x<tam; x++)
        for(int y=0; y<tam; y++)
        {
            matriz[x][y]--;
            if(matriz[x][y] < 0)
               matriz[x][y] = 9;
        }
}

void transpose(int tam)
{
    for(int x=0; x<tam; x++)
        for(int y=0; y<tam; y++)
            tmpMatriz[y][x] = matriz[x][y];
    for(int x=0; x<tam; x++)
        for(int y=0; y<tam; y++)
            matriz[x][y] = tmpMatriz[x][y];
}

void swapRow(int r1, int r2, int tam)
{
    for(int x=0; x<tam; x++)
        swap(matriz[r1][x], matriz[r2][x]);
}

void swapCol(int r1, int r2, int tam)
{
    for(int x=0; x<tam; x++)
        swap(matriz[x][r1], matriz[x][r2]);
}

int main()
{
    int casos, tam, queries, r1, r2;
    string str;

    scanf("%d", &casos);
    for(int i=1; i<=casos; i++)
    {
        scanf("%d", &tam);
        readMatrix(tam);

        scanf("%d", &queries);
        for(int j=0; j<queries; j++)
        {
            cin>>str;
            if(str == "inc")
               addOne(tam);
            else if(str == "dec")
                    restOne(tam);
            else if(str == "transpose")
                    transpose(tam);
            else if(str == "row")
            {
                scanf("%d %d", &r1, &r2);
                swapRow(r1 - 1, r2 - 1, tam);
            }
            else if(str == "col")
            {
                scanf("%d %d", &r1, &r2);
                swapCol(r1 - 1, r2 - 1, tam);
            }
        }
        printf("Case #%d\n", i);
        print(tam);
    }
return 0;
}

11824 – A Minimum Land Price 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=2924

Greedy and sorting.

How I did it

• I read the number cases.
• I read the prices and put them into a vector until I found a zero.
• I sort the vector in a  non increasing order.
• Traverse the vector and compute the value of the land with the formula given in the problem description.
• If the land price is bigger than 5,000,000 print “Too expensive” otherwise print the lands price.

Hints

•  The most bigger input data can be computed into a int variable.
• We need to sort the data to get the minimum price.
• To compute the price use double variables.

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

bool cmp(int a, int b)
{
    return a>b;
}

int main()
{
    vector<int> vec;
    int casos, val;

    scanf("%d", &casos);
    while(casos--)
    {
        vec.clear();
        while(scanf("%d", &val))
        {
            if(!val)
               break;
            vec.push_back(val);
        }

        sort(vec.begin(), vec.end(), cmp);
        int index = 1;
        double ans = 0.0, tmp;
        for(int i=0; i<vec.size(); i++)
        {
            tmp = 2 * pow(vec[i], index);

            ans = ans + tmp;
            index++;
        }
        if(ans > 5000000)
           printf("Too expensive\n");
        else
            cout<<ans<<endl;
    }
return 0;
}

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;
}