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

12049 – Just Prune The List 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=3200

Data structures, map, set.

How I did it

• I read the number of cases.
• I read the total elements for list 1 and list 2.
• I read the items in the list one. keep a track about the total number of appearances per number in a STL map.
• Insert the current item into a STL set.
• I read the items in the list two. keep a track about the total number of appearances per number in a STL map. (Different maps per list).
• Insert the current item into the STL set.
• Traver the set, and calculate the difference between map1 and map 2 with the current set element.
• Print the answer.

Hints

•  I calculate the different element with the diferent quantity of element for a number in the STL set and O save the appereance of a number in the maps.

Code

#include <cstdio>
#include <cstdlib>
#include <map>
#include <set>
using namespace std;
int main()
{
int casos, l1, l2, val;
scanf("%d", &casos);

while(casos--)
{
    map<int, int> mySet1, mySet2;
    set<int> enums;
    scanf("%d %d", &l1, &l2);
    for(int i=0; i<l1; i++)
    {
        scanf("%d", &val);
        mySet1[val]++;
        enums.insert(val);
    }
    for(int i=0; i<l2; i++)
    {
        scanf("%d", &val);
        mySet2[val]++;
        enums.insert(val);
    }

    int ans = 0, tmp;
    for(set<int>::iterator it=enums.begin(); it!=enums.end(); it++)
    {
        tmp =  abs(mySet1[*it] - mySet2[*it]);
        ans += tmp;
    }
    printf("%d\n", ans);
}
return 0;
}

12646 – Zero or One 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=4375

Ad hoc, complete search.

How I did it

• Read a, b, c.
• Generate all possible scenarios.
• Print the answer.

Hints

•  We have 8 possibles scenarios. ((states a * states b * states c) = 2 * 2 * 2. Because abc can have 0 or 1).
• Possible input: 0 0 0, 0 0 1, 0 1 0, 1 0 0, 0 1 1, 1 0 1, 1 1 0, 1 1 1

Code

#include <stdio.h>
int main()
{
int a,b,c;
while(scanf("%d %d %d", &a, &b, &c) == 3)
{
    if(a == b && b == c)
      printf("*\n");
    else if(a != b && b == c)
            printf("A\n");
    else if(a != b && a == c)
            printf("B\n");
    else if(a == b && a != c)
            printf("C\n");
}
return 0;
}

10505 – Montesco vs Capuleto 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=1446

Graphs, bfs, bipartite graph.

How I did it

• Read the number of cases.
• For each case read the number of nodes.
• Read the graph into a adjacency list.
• Traverse the graph anc call bfs in every not visited node.
• After the call to bfs check if the graph o subgraph is bipartite. If graph is bipartite count the most bigger group (0 or 1) and add it to the total invitations.
• Print the answer.

Hints

•  In the input we can have the subgraphs.
• My code gives AC using C++ 11.

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef vector<int> vi;

vector <vi> graph;
vector<bool> discovered;
vector<int> parent;
vector<int> distances;

bool  isBipartite;
int zero;
int one;

void read_graph(int nodos)
{
    int vertex, enemies;
    int i;
    for(i = 0; i < nodos; i++)
    {
        scanf("%d", &enemies);
        for(int j=0; j<enemies; j++)
        {
            scanf("%d", &vertex);
            graph[i].push_back(vertex - 1);
            graph[vertex - 1].push_back(i);
        }
    }
}

void init(int nodes)
{
    parent.assign(nodes, -1);//stores the nodes ancestor that discovered it for the first time
    distances.assign(nodes, -1);//stores the distance to reach each node from the source
    zero = one = 0;
}

void countVal()
{
    for(int x=0; x<distances.size(); x++)
    {
        if(distances[x] == 0)
           zero++;
        else if(distances[x] == 1)
                one++;
    }
}

void bfs(int start)
{
    int current;//current node being processed
    int next;//reached node by current
    unsigned int i;
    queue<int> vertices;//vertices to process
    distances[start] = 0;
    discovered[start] = true;
    vertices.push(start);
    isBipartite = true;

    while(!vertices.empty())
    {
        current = vertices.front();
        vertices.pop();
        for(i = 0; i < graph[current].size(); i++)//for each node connected to current
        {
            next = graph[current][i];
            if(!discovered[next])//if it hasn't been reached
            {
                discovered[next] = true;//mark it as reached
                parent[next] = current;//store its parent
                distances[next] = 1 - distances[current];//save the distance
                vertices.push(next);//push it to the queue for further analysis
            }
            else if(distances[next] == distances[current])
            {
                isBipartite = false;
                //break;
            }
        }
    }
}

/*void print()
{
    for(int c=0; c<graph.size(); c++)
    {
        cout<<"Node "<<c<<":";
        for(int d=0; d<graph[c].size(); d++)
        {
            cout<<graph[c][d]<<" ";
        }
        cout<<endl;
    }

}*/

int main()
{
int casos, nodes, total;
scanf("%d", &casos);
while(casos--)
{
    total = 0;
    scanf("%d", &nodes);
    graph.assign(nodes, vi());
    discovered.assign(nodes, false);
    read_graph(nodes);
    init(nodes);
    //print();
    for(int x=0; x<graph.size(); x++)
    {
        if(discovered[x] == false)
        {
            init(nodes);
            bfs(x);
            //print();
            //cout<<"Node call "<<x<<endl;
            //for(int g=0; g<distances.size(); g++)
              //  cout<<distances[g]<<" ";
            //cout<<endl;
            if(isBipartite)
            {
                countVal();
                int tmp = max(zero, one);
                total += tmp;
            }
        }
    }
    printf("%d\n", total);
}
return 0;
}

12247 – Jollo 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=3399

Ad hoc,  complete search, data structures.

How I did it

• Read the cards from the princess, read the cards from the prince.
• If the cards are equal to 0 stop the program.
• Generate all possible games with the cards. (12 possibles games).
• For every game find the lowest card to win the game and save that card in a set of probable answers.
• In all possible games try every possible answer and check if is enough to win every game.(12 games).
• Print the answer.

Hints

•  Generate all possible games. (Always 12)
• The possible status of a game for prince:  Win Win, Win Lose, Lose Win, Lose Lose.
• If we have a game Lose Lose, print -1.

Critical Input

1 2 3 51 52

Critical Output

4

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <bitset>
#include <set>
using namespace std;
typedef pair<int,int> ii;

struct game
{
    ii p1;
    ii p2;
    ii p3;
};

vector<int>girl,boy;
vector<game> gameArray;
bitset<54> myCards;
set<int> mySet;

bool isWW(int pos)
{
    game tmp = gameArray[pos];

    if(tmp.p1.first < tmp.p1.second && tmp.p2.first < tmp.p2.second)
       return true;
    else
        return false;
}

vector<int> getNotUsed(int x, vector<int>vec)
{
    vector<int> ans;

    for(int a=0; a<vec.size(); a++)
        if(x!=a)
           ans.push_back(vec[a]);
return ans;
}

void generate()
{
    vector<int> nGirl, nBoy;
    for(int x=0; x<girl.size(); x++)
    {
        for(int y=0; y<boy.size(); y++)
        {
            ii p1 = make_pair(girl[x], boy[y]);

            nGirl = getNotUsed(x,girl);
            nBoy  = getNotUsed(y, boy);

            ii p2 = make_pair(nGirl[0], nBoy[0]);
            ii p3 = make_pair(nGirl[1], -1);

            game g1, g2;
            g1.p1 = p1;g1.p2 = p2;g1.p3 = p3;
            gameArray.push_back(g1);

            p2 = make_pair(nGirl[1], nBoy[0]);
            p3 = make_pair(nGirl[0], -1);
            g2.p1 = p1;g2.p2 = p2;g2.p3 = p3;
            gameArray.push_back(g2);
        }
    }
}

void print()
{
    for(int u=0; u<gameArray.size(); u++)
    {
        game tmp = gameArray[u];
        cout<<"Res\n";
        cout<<tmp.p1.first<<"  "<<tmp.p1.second<<endl;
        cout<<tmp.p2.first<<"  "<<tmp.p2.second<<endl;
        cout<<tmp.p3.first<<"  "<<tmp.p3.second<<endl<<endl;
    }
}

bool impossible()
{
    int cont;
    for(int x=0; x<gameArray.size(); x++)
    {
        game tmp = gameArray[x];
        cont = 0;
        if(tmp.p1.first > tmp.p1.second)
           cont++;
        if(tmp.p2.first > tmp.p2.second)
           cont++;

        if(cont == 2)
           return true;
    }
return false;
}

int getProbAnswer()
{
    for(int i=1; i<=52; i++)
        if(!myCards.test(i))
           return i;
return -1;
}

int getProbVal(int u)
{
    game tmp = gameArray[u];
    int card = tmp.p3.first;

    for(int i=card; i<=52; i++)
        if(!myCards.test(i))
           return i;
return -1;
}

int getAnswer()
{
    set<int>:: iterator it;
    bool flag;
    int tmp,card;
    for(it=mySet.begin(); it!=mySet.end(); it++)
    {
        tmp = (*it);
        if(tmp == -1)
           return -1;

        flag = true;
        for(int a=0; a<gameArray.size(); a++)
        {
            if(isWW(a))
               continue;
            game g1 = gameArray[a];
            card = g1.p3.first;

            if(tmp < card)
            {
                flag = false;
                break;
            }
        }
        if(flag)
           return tmp;
    }
return -1;
}

int main()
{
int a,b,c,x,y, tmpAnswer, answer;
while(scanf("%d %d %d %d %d", &a, &b, &c, &x, &y))
{
    if(!a && !b  && !c  && !x  && !y)
       break;

    girl.clear(),boy.clear();gameArray.clear();
    girl.push_back(a);girl.push_back(b);girl.push_back(c);
    boy.push_back(x);boy.push_back(y);
    myCards.reset();
    mySet.clear();
    myCards.set(a, 1);myCards.set(b, 1);myCards.set(c, 1);myCards.set(x, 1);myCards.set(y, 1);
    generate();
    //print();
    if(impossible())
       printf("-1\n");
    else
    {
        for(int u=0; u<gameArray.size(); u++)
        {
            if(isWW(u))
            {
                tmpAnswer = getProbAnswer();
                mySet.insert(tmpAnswer);
            }
            else
            {
                tmpAnswer = getProbVal(u);
                mySet.insert(tmpAnswer);
            }
        }
        /*cout<<"Posibles respuestas";
        for(set<int>::iterator it=mySet.begin(); it!=mySet.end(); it++)
            cout<< *it <<" ";
        cout<<endl;*/
        answer = getAnswer();
        printf("%d\n", answer);
    }
}
return 0;
}

11683 – Laser Sculpture 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=2730

Ad hoc, linear scan.

How I did it

• Read the number of rows and columns. If row == 0 and columns = 0 stop the program.
• Read the final heigth and insert this values inside a vector.
• Traverse the vector. If is the first time save the diference between the row and current vector position(set current equal to vector current position), otherwise if the current vector position  is less than current variable save the diference between current and the current vector position.
• Print the total.

Hints

•  Simulate the process will finish in TLE.
• To solve thism problem a linear scan is enough.

Code

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int main()
{
int row, col, val, current, tot;

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

    vector<int> vec;
    tot = 0;

    for(int x=0; x<col; x++)
    {
        scanf("%d", &val);
        vec.push_back(val);
    }

    for(int y=0; y<vec.size(); y++)
    {
        if(y == 0)
        {
            tot = row - vec[y];
            current = vec[y];
        }
        else
        {
            if(vec[y] < current)
               tot = tot + (current - vec[y]);
        }
        current = vec[y];
    }
    printf("%d\n", tot);
}

return 0;
}

11631 – Dark roads 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=2678

Graphs, kruskal, minimum spanning tree.

How I did it

• Read the number of vertices and edges.
• Read the graph as a Edge list. (node 1 , node 2,weight)
• Call kruskal.
• Calculate all the weight from the graph and substract the minimum cost of the spanning tree.
• Print the value.

Hints

• This algorithm use union find disjoint sets.

Code

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

#define    V        200001
#define    E        200001

using namespace std;

int tree[V];
int rank[V];
long long costoTotal;
struct edge
{
    int from, to;
    int weight;
    bool operator < (const edge &other) const
    {
        return weight < other.weight;
    }
};

vector<edge> edges;

void initialize(int nodes)
{
    int i;
    for(i = 0; i <= nodes; i++)
    {
        tree[i] = i;
        rank[i] = 1;
    }
    edges.clear();
}

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

void union_sets(int x, int y)
{
    int rx, ry;
    rx = find_set(x);
    ry = find_set(y);
    if(rx == ry)
        return;
    if(rank[rx] > rank[ry])
    {
        rank[rx] += rank[ry];
        tree[ry] = rx;
    }
    else
    {
        rank[ry] += rank[rx];
        tree[rx] = ry;
    }
}

int kruskal()//returns the MST weight
{
    int total; //the weight of MST
    int u, v; //vertices in each edge
    int i;
    sort(edges.begin(), edges.end());
    total = 0;
    for(i = 0; i < edges.size(); i++)
    {
        u = find_set(edges[i].from);
        v = find_set(edges[i].to);
        if(u != v)
        {
            union_sets(u,v);
            total += edges[i].weight;
        }
    }
    return total;
}

void read_graph(int number_of_edges)
{
    int i;
    edge e;
    for(i = 0; i < number_of_edges; i++)
    {
        scanf("%d %d %d", &e.from, &e.to, &e.weight);
        costoTotal+= e.weight;
        edges.push_back(e);
    }

}int main()
{
    int nodes;
    int number_of_edges;
    while(scanf("%d %d", &nodes, &number_of_edges))
    {
        if(!nodes && !number_of_edges)
           break;
        costoTotal = 0;
        initialize(nodes);
        read_graph(number_of_edges);
        cout<<costoTotal - kruskal()<<endl;
    }
return 0;
}

895 – Word Problem 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=836

Strings, ad hoc, input parsing, sstream.

How I did it

• I read the dictionary words inside a vector until I found “#”.
• I read the request queries until I found another “#”.(stringstream).
• I check word by word if  can I get the word from the dictionary.
• If a word can be formed increment a counter.
• Print the counter value.

Hints

• We can use a backtracking approach to check all the possible results.
• The input is not bigger.
• Read with getline and parse the input with sstream.

Code

#include <iostream>
#include <cstdio>
#include <sstream>
#include <vector>
using namespace std;
vector<string> dictionary;
vector<char> letter;
vector<int> status;
int cont;

void checkInput()
{
string current;
bool flag;
    for(int x=0; x<dictionary.size(); x++)
    {
        current = dictionary[x];
        status.assign(letter.size(), 0);
        for(int y=0; y<current.size(); y++)
        {
            flag  = false;
            for(int z=0; z<letter.size(); z++)
            {
                if(current[y] == letter[z] && status[z] == 0)
                {
                    status[z] = 1;
                    flag = true;
                    break;
                }
            }
            if(flag == false)
               break;
        }
        if(flag)
           cont++;
    }
}

int main()
{
string str;
char data;
stringstream ss;

while(getline(cin, str))
{
    if(str == "#")
       break;
    dictionary.push_back(str);
}
while(getline(cin,str))
{
    if(str == "#")
       break;
    stringstream ss;
    cont = 0;

    ss<<str;

    while(ss>>data)
        letter.push_back(data);

    //for(int c=0; c<dictionary.size(); c++)
    //    cout<<dictionary[c]<<" "<<endl;
    //cout<<endl;

    //for(int c=0; c<letter.size(); c++)
     //   cout<<"To->"<<letter[c]<<" ";
    //cout<<endl;

    checkInput();
    printf("%d\n", cont);
    letter.clear();
}
return 0;
}