Sort! Sort! and Sort! Uva solution 11321

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=2296

How I did it

• Read the numbers to sort, and the module.
• Insert the number into a vector.
• Sort the vector with a modified comp.
• Print the numbers.

Hints

• The order is decided with  the module value.
• Is two numbers has the same module value, the order is decided with the number value.
• Careful with the negative numbers.

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstdlib>
using namespace std;
int  modulo;
bool cmp(int a, int b)
{
    if(a%modulo != b%modulo)
       return a%modulo < b%modulo;
    else
    {
        if(abs(a)%2 == 0 && abs(b)%2 == 0)
          return a<b;
        else if(abs(a)%2 != 0 && abs(b)%2 != 0)
                return a>b;
        else if(abs(a)%2 != 0)
                return true;
        else
            return false;
    }
}

int main()
{
int number, data;
while(scanf("%d %d", &number, &modulo))
{
    printf("%d %d\n", number, modulo);
    if(!number && !modulo)
       break;
    vector<int> vec;
    for(int x=1; x<=number; x++)
    {
        scanf("%d", &data);
        vec.push_back(data);
    }
    sort(vec.begin(),vec.end(),cmp);
    for(int y=0; y<vec.size(); y++)
        printf("%d\n", vec[y]);
}
return 0;
}

Marvelous Mazes UVA 445

This is an easy problem from uva judge. http://uva.onlinejudge.org/external/4/445.htmlHow I did it

• Read line by line .
• Traverse the line. First get the number of times that we need to repeat a character. Second get the character to repeat.
• Print the character the number of times that I obtained.
• When we finish the traversal of the string, print a blank line.

Hints

• The last input case has not a blank line.
• Be careful with the line between input and output.

Code

#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;
int main()
{
string cad;
while(getline(cin,cad))
{
    int index = 0, number  = 0;
    while(index < cad.size())
    {
        if(isdigit(cad[index]))
           number += (cad[index] - '0');
        else if(isalpha(cad[index])  ||  cad[index] == '*')
        {
            for(int x=1; x<=number; x++)
            {
                if(cad[index] == 'b')
                   cout<<' ';
                else
                    cout<<cad[index];
            }
            number = 0;
        }
        else if(cad[index] == '!')
            cout<<'\n';
    index++;
    }
    cout<<'\n';
}
return 0;
}

Birthdates UVA solution 12541

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=3986

Sorting problem.

How I did it

• Read the number of people .
• Read the name, day, month and year of the people.
• Set a Person object and insert into a vector<Person>.
• Use STL sort function with bool comparation.(sort a vector o Person structure).
• Print the first and last element of the array.

Hints

• The input is really small.
• All the dates are diferents.

Code

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

struct Person{
string name;
int day, month, year;
};

bool cmp(Person x, Person y)
{
    if(x.year > y.year)// Validate year
       return true;
    else if(x.year < y.year)
        return false;
    else if(x.month > y.month)//Validate month
        return true;
    else if(x.month < y.month)
        return false;
    else if(x.day > y.day)//Validate day
        return true;
    else if(x.day < y.day)
        return false;
}

int main()
{
int people, day, month, year;
string name;
vector<Person> personVector;
Person older, younger;

scanf("%d", &people);
for(int x=1; x<=people; x++)
{
    cin>>name;
    scanf("%d %d %d", &day, &month, &year);
    Person obj;
    obj.name  = name;
    obj.day   = day;
    obj.month = month;
    obj.year  = year;

    personVector.push_back(obj);
}
sort(personVector.begin(), personVector.end(), cmp);

older     = personVector[0];
younger   = personVector[personVector.size()-1];

printf("%s\n%s\n", older.name.c_str(), younger.name.c_str());
return 0;
}

Forests Solution UVA 10227

This is an easy problem from uva judge, but has a tedious implementation. http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1168

Union find disjoint sets.

How I did it

• Read the number of cases .
• Read the total number of people and trees.
• Read and sort the opinion of the people as a graph data structure. Vector vector of set. (opinionGraph)
• Initialize the parent array with the number of people who will listen the fall of trees. (parent is the disjoint set representation).
• Traverse the opinionGraph with 2 fors. If I found 2 equal sets I do union sets.
• I traverse the parent array and check the diferents sub set and insert into an answer set. (This set has the answer the diferents opinions)
• I print the answer set size.

Hints

• Read carefully what does mean opinion of the people.
• We don’t now how many inputs we will have. I am using sstream to parse the input.
• Union find algorithm is really usefull.
• The out is separated by a blank line between 2 consecutive inputs. In the last input we must not print the blank line.

Input analisis
3 4
1 2
3 3
1 3
2 2
3 2
2 4

Code

#include <iostream>
#include <cstdio>
#include <sstream>
#include <vector>
#include <set>
#include <algorithm>
#define ELEMENTS 110
using namespace std;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef set<int>   vi;

vector<vi> opinionGraph;
int parent[ELEMENTS];
int rank[ELEMENTS];

void make_sets(int 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];
}

void set_union(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];
        parent[ry] = rx;
    }
    else
    {
        rank[ry] += rank[rx];
        parent[rx] = ry;
    }
}

void read_graph()
{
    //opinionGraph.clear();
    string str;
    stringstream ss;
    int people, tree, data;

    while(getline(cin,str))
    {   int flag = 0;
        if(str.size() == 0)
           return;
        ss<<str;
        while(ss>>data)
        {
            if(!flag)
            {
                people = data;
                flag = 1;
            }
            else
                tree = data;
        }
        ss.clear();
        //cout<<people<<"  "<<tree <<people*2<<endl;
        opinionGraph[people-1].insert(tree-1);
    }
}

int main()
{
int casos,people, trees;
string trash;

scanf("%d", &casos);
getline(cin,trash);//Reading until en of line after casos
getline(cin,trash);//Reading the first empty line
while(casos--)
{
    scanf("%d %d",&people, &trees);
    opinionGraph.assign(people, vi());
    getline(cin,trash);
    read_graph();

    //Strating union find
    make_sets(people);
    for(int x=0 ; x<opinionGraph.size(); x++)
        for(int y=x+1 ; y<opinionGraph.size(); y++)
           if(opinionGraph[x] == opinionGraph[y])
               set_union(parent[x], parent[y]);

    for(int g=0; g<people; g++)
        parent[g] = find_set(g);

    int total = 0;
    set<int>answer;
    for(int h=0; h<people; h++)
        answer.insert(parent[h]);

    printf("%d\n",answer.size());
    if(casos)
      printf("\n");
}
return 0;
}

Word Length and Frequency 10293

This is an easy problem from uva judge http://uva.onlinejudge.org/external/102/10293.html

Ad hoc problem.

How I did it

• Read line by line the strings while the first character of the string is diferent to # .
• Iterate throught the string searching the characters that are alphabetics and saving the length of the current word.
• If I find a space separator character (” ” ,? ,! ,. ,’,’) I save the current length of a word in a map<int, int> where the key is the size of the word and the value the number of word with the size of the key. Reset the word size variable.
• If I find the # character as first character of a line, we print the map content.
• Clean map, clear flag variables and print a blank line.

Hints

• The input is small, a brute force aproach is enough.
• The length of the word is only composed by alphabetic characters.
• Consider this type of case as only a word:  you’ve  length = 5.
• The space separators are: ” “, ?, !, ., , .
• Print a blank line after each block.
• And end block could be : #this is the end of block

Code

#include <iostream>
#include <cstdio>
#include <map>
#include <cctype>
using namespace std;
int main()
{
string cad;
map<int,int> myMap;
int wSize = 0;
while(getline(cin,cad))
{
    if(cad[0] != '#')
    {
        for(int a=0; a<cad.size(); a++)
        {
            if(isalpha(cad[a]))
               wSize++;
            else if(isspace(cad[a]) || cad[a] == '!' || cad[a] == '?' || cad[a] == ',' || cad[a] == '.')
            {
                myMap[wSize]++;
                wSize = 0;
            }
        }
        if(cad[cad.size()-1] != '-' && wSize>0)
        {
            myMap[wSize]++;
            wSize = 0;
        }
    }
    else
    {   map<int,int>::iterator it = myMap.begin();
        if(it->first == 0)
            it++;
        for(it = it; it!= myMap.end(); it++)
            printf("%d %d\n",it->first,it->second);
        printf("\n");
        wSize = 0;
        myMap.clear();
    }
}
return 0;
}