100 – The 3n + 1 problem 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=36

Brute Force, Iterative, Complete search.

How I did it

• I read i and j.
• I save the values of i and j in oi = i and oj =j. (Just for the output).
• If i is greater than j swap i and j.
• Traverse i to j and calculate the cycle length of the current number.
• Save the max length cycle.
• Print oi, oj and the max length cycle.
• Accepted! 😀

Hints

• j can be greater than i.
• Print i and j in the original order. Print j i will give us wrong answer.

Code

#include <bits/stdc++.h>

using namespace std;

int  getCycle(int n)
{
    int cont = 1;

    while(n != 1)
    {
        if(n%2 != 0)
          n = n*3 + 1;
        else
            n/=2;
        cont++;
    }
return cont;
}

int main()
{
    int i,j, cycleL, ans;
    int io, jo;

    while(scanf("%d %d", &i, &j) != EOF)
    {
        io = i, jo = j;

        if(i > j)
           swap(i,j);

        ans = -1000;
        for(int x=i; x<=j; x++)
        {
            cycleL = getCycle(x);
            ans = max(cycleL, ans);
        }

        printf("%d %d %d\n", io, jo, ans);
    }
return 0;
}

12583 – Memory Overflow 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=4028

Iterative Complete search.

How I did it

• I read the number of cases.
• Red the number of people, the days to remember(rem) and the group of people who remember (str string in my case).
• Traverse the str string. First check if the current person is remembered(map<char,int>), if the map value is greater than 0, increment the recognition with one.
• I traverse the map and decrease all element with -1. (One day less).
• Set the current element in the map with the (rem) days.
• Print the recognitions.
• Accepted! 😀

Hints

• You need to check the last (rem) days in the current day.
• If the sultan remember a person the map[char] is greater than 0..

Code

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int casos, people, rem;
    int recog;
    string str;
    char meet;
    map<char,int>mapa;

    scanf("%d", &casos);

    for(int i=1; i<=casos; i++)
    {
        scanf("%d %d", &people, &rem);
        cin>>str;

        recog = 0;

        for(int x=0; x<str.size(); x++)
        {
            meet = str[x];
            if(mapa[meet]>0)
                recog++;

            for(map<char,int>::iterator it=mapa.begin(); it!=mapa.end(); it++)
                mapa[it->first]--;
            mapa[meet] = rem;
        }
        printf("Case %d: %d\n", i, recog);
        mapa.clear();
    }
return 0;
}

12207 – That is Your Queue 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=3359

Data structures, Linked List.

How I did it

• I read the number of elements and queries.
• If the number of elements is equal or less than 1000 I push the number of element into a linked list, otherwise I push 1000 elements.
• Read the queries, if the querie is  “N” print the front element of the list and pop the element and push it into the tail. If the querie is “E” read the value, remove the value from the list and push in the front of the list.

Hints

• When the querie is E I dont print any value.
• I initialize the list at most 1000 elements because the number of queries are 1000, and the idea is handle a queue.
• If you initialize the linked list, deque or queue with 1000000000 you will get time limit.

Code

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

using namespace std;

list<int> lista;

void init(int N)
{
    lista.clear();
    int lim = min(N, 1000);
    for(int i=1; i<=lim; i++)
        lista.push_back(i);
}

int main()
{
    int dim, queries, pos, tmp, casos = 1;
    char ins;
    while(scanf("%d %d", &dim, &queries))
    {
        if(!dim && !queries)
           break;

        init(dim);
        printf("Case %d:\n", casos++);
        for(int i=1; i<=queries; i++)
        {
            cin>>ins;
            if(ins == 'N')
            {
                tmp = lista.front();
                printf("%d\n", tmp);
                lista.pop_front();

                //if(dim <= 1000)
                  lista.push_back(tmp);
            }
            else
            {
                scanf("%d", &pos);
                lista.remove(pos);
                lista.push_front(pos);
            }
        }
    }
return 0;
}

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