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