489 – Hangman Judge 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=430

Adhoc.

How I did it

• Read the round number.
• Read answer and the guess string.
• Traverse the guess string and search each character in the answer string. If more than 6 characters are not found in the answer array, the player lose(break the loop). If all the answer characters were founded, the player wins(break the loop).
• Print the result.

Hints

• check 2 conditions:     a) Once that the wrong guesses is equal to 7 break the loops.  b) Once that all the characters were found, break the loops.
• If one condition is full filled, you need to break the loops and tests(win or loose). Otherwise end the loops(chickened out).

Code

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

bool checkStatus(vector<int>estados)
{
    for(int v=0; v<estados.size(); v++)
        if(estados[v] == 0)
           return false;
return true;
}

int main()
{
vector<int> estados;
string answer, guess;
int round;

while(scanf("%d", &round))
{
    if(round == -1)
       break;

    cin>>answer;
    cin>>guess;

    bool flagProb = true, flag;
    estados.assign(answer.size(), 0);
    set<char> wrong;

    for(int x=0; x<guess.size(); x++)
    {
        flag = false;
        for(int y=0; y<answer.size(); y++)
            if(guess[x] == answer[y])
            {
                flag = true;
                estados[y] = 1;
            }
        if(!flag)
        {
            wrong.insert(guess[x]);
            if(wrong.size() == 7)
            {
                flagProb = false;
                break;
            }
        }
        if(checkStatus(estados))
        {
            flagProb =  true;
            break;
        }
    }
    printf("Round %d\n", round);
    if(!flagProb)
       printf("You lose.\n");
    else if(checkStatus(estados))
            printf("You win.\n");
    else
        printf("You chickened out.\n");
}
return 0;
}

10189 – Minesweeper 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=1130

Adhoc.

How I did it

• Read the row and column size.
• Read the input matriz, set an output matriz with 0s.
• Traverse the input matriz. If the current cell is ‘*’. check if all the posible adjacent cell are diferents than ‘*’ and increment the value in the output matriz.
• Just print the output matrix.

Hints

• Print a blank line between cases. The last case does not need the blank line.
• The 8 posible adjacent cells are:

  [a-1][b], [a-1][b+1], [a-1][b-1], [a+1][b+1], [a+1][b-1], [a+1][b], [a][b-1], [a][b+1].

Code

#include <iostream>
#include <cstdio>
#define MAX 101
using namespace std;
char input[MAX][MAX];
int  output[MAX][MAX];

void readMatriz(int row, int col)
{
    string tmp = "", dataRow;
    for(int x=1; x<=row; x++)
    {
        cin>>dataRow;
        tmp+=dataRow;
    }

    int index = 0;
    for(int x=0; x<row; x++)
        for(int y=0; y<col; y++, index++)
        {
            input[x][y] = tmp[index];
            output[x][y] = 0;
        }
}

void getResult(int row, int col)
{
    for(int a=0; a<row; a++)
    {
        for(int b=0; b<col; b++)
        {
            //////////////////////////////////////////////////////////////////////////
            if(input[a][b] == '*')
            {
                if(a-1 >= 0)
                {
                    if(input[a-1][b] != '*')
                       output[a-1][b]++;

                    if(b+1 < col && input[a-1][b+1] != '*')
                      output[a-1][b+1]++;
                    if(b-1 >= 0 && input[a-1][b-1] != '*')
                       output[a-1][b-1]++;
                }
                if(a+1 < row)
                {
                    if(b+1 < col && input[a+1][b+1] != '*')
                       output[a+1][b+1]++;
                    if(b-1 >= 0 && input[a+1][b-1] != '*')
                        output[a+1][b-1]++;
                    if(input[a+1][b] != '*')
                        output[a+1][b]++;
                }
                if(b-1 >= 0 && input[a][b-1] != '*')
                   output[a][b-1]++;
                if(b+1 < col && input[a][b+1] != '*')
                    output[a][b+1]++;
            }
            ////////////////////////////////////////////////////////////////////////
        }
    }
}

void print(int row, int col)
{
    for(int x=0; x<row;x++)
    {
        for(int y=0; y<col; y++)
        {
                 if(input[x][y] == '*')
                    printf("*");
                 else
                     printf("%d", output[x][y]);
        }
        printf("\n");
    }
}

int main()
{
int row, col, casos = 0;

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

    readMatriz(row, col);
    getResult(row, col);
    if(casos == 0)
       casos++;
    else
        printf("\n");
    printf("Field #%d:\n", casos++);
    print(row, col);
}
return 0;
}

10945 – Mother bear 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=1886

Adhoc, palindromes stl.

How I did it

• Read the number of cases.
• Read the string.
• Only save the letters in other string.
• If the string and the rever string are equal print “You won’t be eaten!”. Otherwise print “Uh oh ..”.

Hints

• Really easy using cctype and algorithm libraries.
• Ignore all the characters diferents than letters.

Code

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

int main()
{
string str;
while(getline(cin,str))
{
    if(str == "DONE")
       break;

    string outR = "", out;
    for(int x=0; x<str.size(); x++)
        if(isalpha(str[x]))
            outR += tolower(str[x]);

    out = outR;
    reverse(outR.begin(), outR.end());
    if(outR == out)
      printf("You won't be eaten!\n");
    else
        printf("Uh oh..\n");
}
return 0;
}

10190 – Divide, But Not Quite Conquer! 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=1131

Complete search, strings.

How I did it

• Read the n and m until reach EOF.
• If n<2 or m<2 or m>n. Print Boring.(This gives me TLE and RTE).
• Otehrwise simulate the process.
• If you can develop the sequence print it otherwise print boring.

Hints

• n and m are non negative numbers. Careful with n, m = 1 or n,m =0;

Code

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

int main()
{

long n, m;
bool flag;
while(cin>>n>>m)
{
    vector<long> vec;
    flag = true;
    vec.push_back(n);
    if( m <2 || n < 2 || m>n)
       printf("Boring!\n");
    else
    {
        while(n != 1)
        {
            if(n%m == 0)
            {
                n/=m;
                vec.push_back(n);
            }
            else
            {
                flag = false;
                break;
            }
        }
            if(flag)
            {
                for(long x=0; x<vec.size(); x++)
                {
                    if(x < vec.size() - 1)
                       printf("%ld ", vec[x]);
                    else
                        printf("%ld\n", vec[x]);
                }
            }
            else
                printf("Boring!\n");
    }
}
return 0;
}

10887 – Concatenation of Languages 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=1828

Complete Search, strings.

How I did it

• Read the number of cases
• Read the size of group 1 and group 2.
• Read the elements of group1 and group 2.
• With 2 fors nested generate al the posible words and insert into a STL set.
• Print the size of the set.

Hints

• New String = strings of the second language + strings of the first language.

Code

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

int main()
{
int casos, g1, g2;
string str;

scanf("%d", &casos);
for(int v=1; v<=casos; v++)
{
    vector<string> vec1, vec2;
    set<string> mySet;
    scanf("%d %d", &g1, &g2);
    getline(cin,str);

    for(int x=1; x<=g1; x++)
    {
        getline(cin,str);
        vec1.push_back(str);
    }
    for(int x=1; x<=g2; x++)
    {
        getline(cin,str);
        vec2.push_back(str);
    }

    string tmp;
    for(int x=0; x<vec1.size(); x++)
        for(int y=0; y<vec2.size(); y++)
        {
            tmp = vec1[x] + vec2[y];
            mySet.insert(tmp);
        }
    printf("Case %d: %d\n", v, mySet.size());
}
return 0;
}

12149 – Feynman 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=3301

Ad hoc.

How I did it

• Generate all the possibles scenarios
• Read the size of the square.
• Print the result.

Hints

• There is a pattern.
• The size is really small.

Code

#include <iostream>
#include <cstdio>
using namespace std;
int vec[120], out[120];

void generate()
{
    int increment = 3;
    vec[0] = 1;
    out[0] = 1;

    for(int x=1; x<=102; x++, increment = increment + 2)
    {
        vec[x] = vec[x-1] + increment;
        out[x] = out[x-1] + vec[x];
    }
}

int main()
{
int num;
generate();
while(scanf("%d", &num))
{
    if(!num)
       break;

    printf("%d\n", out[num-1]);
}
return 0;
}

11396 – Claw Decomposition 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=2391

Graphs, Breadth First Search, bicolorable, check bipartie graph.

How I did it

• Read the number vertices.
• Read the number the edges until 0 0 is founded.
• Call bfs(0) and check if is bipartite.

Hints

• A little variant in bfs is enough to check if a graph is bipartite.

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define MAXN 202
using namespace std;
typedef vector<int> vi;

vector < vector <int> > graph;
vector<bool> discovered;//keeps track if a node has been reached
vector<int> parent;//stores the nodes ancestor that discovered it for the first time
vector<int> distances;//stores the distance to reach each node from the source
bool  isBipartite;

void read_graph(int edges)
{
    int vertex1,  vertex2;
    int i;
    while(scanf("%d %d", &vertex1, &vertex2))
    {
        if(!vertex1 && !vertex2)
           break;
        graph[vertex1-1].push_back(vertex2-1);
        graph[vertex2-1].push_back(vertex1-1);
    }
}

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() && isBipartite)
    {
        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 find_path(int vertex)//recursive procedure to find the path
{
    if(vertex == -1)
        return;
    find_path(parent[vertex]);
    printf("%d ", vertex);
}

int main()
{
int vertices, edges;
while(scanf("%d", &vertices))
{
    if(!vertices)
       break;
    graph.assign(vertices, vi());
    discovered.assign(vertices, false);
    distances.assign(vertices, -1);
    parent.assign(vertices, -1);

    read_graph(edges);
    bfs(0);
    if(isBipartite)
       printf("YES\n");
    else
        printf("NO\n");
}
return 0;
}

10004 – Bicoloring 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=945

Graphs, Breadth First Search, bicolorable, check bipartie graph.

How I did it

• Read the number vertices.
• Read the number of edges.
• Read the graph.
• Call bfs(0) and check if is bipartite.

Hints

• A little variant in bfs is enough to check if a graph is bipartite.

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define MAXN 202
using namespace std;
typedef vector<int> vi;

vector < vector <int> > graph;
vector<bool> discovered;//keeps track if a node has been reached
vector<int> parent;//stores the nodes ancestor that discovered it for the first time
vector<int> distances;//stores the distance to reach each node from the source
bool  isBipartite;

void read_graph(int edges)
{
    int vertex1,  vertex2;
    int i;
    for(i = 0; i < edges; i++)
    {
        scanf("%d %d", &vertex1, &vertex2);
        graph[vertex1].push_back(vertex2);
        graph[vertex2].push_back(vertex1);
    }
}

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() && isBipartite)
    {
        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 find_path(int vertex)//recursive procedure to find the path
{
    if(vertex == -1)
        return;
    find_path(parent[vertex]);
    printf("%d ", vertex);
}

int main()
{
int vertices, edges;
while(scanf("%d", &vertices))
{
    if(!vertices)
       break;
    scanf("%d", &edges);
    graph.assign(vertices, vi());
    discovered.assign(vertices, false);
    distances.assign(vertices, -1);
    parent.assign(vertices, -1);    read_graph(edges);
    bfs(0);
    if(isBipartite)
       printf("BICOLORABLE.\n");
    else
        printf("NOT BICOLORABLE.\n");
}
return 0;
}

762 – We Ship Cheap 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=703

Graphs, Breadth First Search, Single source shortest path(SSSP).

How I did it

• Read the number of cities that has an edge.
• Read the origen and destination city.
• Set the graph.
• If origen and destination are present in the graph call bfs. Otherwise print No route.
• If distance of destination is -1(No reachable from origen) cal find path.
• Print the path.

Hints

• I got 4 runtime errors. The origen and destination cities are not necessarily in the graph

Input

3
JV PT
KA PT
KA HP
JV HP

2
JV PT
KA HP
JV HP

0
AA BB

1
AA BB
CC BB

1
AA BB
GG PP

2
AA BB
BB CC
GG GG

4
AB JK
PO LK
QW PO
LK AB
AB PO

Output

JV PT
PT KA
KA HP

No route

No route

No route

No route

AB LK
LK PO

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
#include <set>

using namespace std;

map <int, vector <int> > graph;
map<int,bool> discovered;//keeps track if a node has been reached
map<int,int>  parent;//stores the nodes ancestor that discovered it for the first time
map<int,int>  distances;//stores the distance to reach each node from the source
//For read the data
vector<pair<string,string> > edgesVec;
set<string> mySet;
map<string,int> vec;
vector<string> output;
vector<int> outputId;

void readEdges(int edges)
{
    string c1, c2;
    for(int x=1; x<=edges; x++)
    {
        cin>>c1>>c2;
        pair<string,string> p = make_pair(c1,c2);
        edgesVec.push_back(p);
        mySet.insert(c1);mySet.insert(c2);
    }
}

void setId()
{
    int index = 0;
    for(set<string>::iterator it=mySet.begin(); it!=mySet.end(); it++, index++)
        vec[*it] = index;
}

void read_graph()
{
    //graph.clear();
    int i, vertex1, vertex2;
    string el1, el2;
    for(i = 0; i < edgesVec.size(); i++)
    {
        el1 = edgesVec[i].first;
        el2 = edgesVec[i].second;
        vertex1 = vec[el1];
        vertex2 = vec[el2];

        graph[vertex1].push_back(vertex2);
        graph[vertex2].push_back(vertex1);

        discovered[vertex1] = false;discovered[vertex2] = false;
        parent[vertex1] = -1;parent[vertex2] = -1;
        distances[vertex1] = -1;distances[vertex2] = -1;
    }
}

void clearGraph()
{
    graph.clear();
    discovered.clear();//keeps track if a node has been reached
    parent.clear();//stores the nodes ancestor that discovered it for the first time
    distances.clear();//stores the distance to reach each node from the sour
    edgesVec.clear();
    mySet.clear();
    vec.clear();
    output.clear();
    outputId.clear();
}

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);
    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] = distances[current]+1;//save the distance
                vertices.push(next);//push it to the queue for further analysis
            }
        }
    }
}

void find_path(int vertex)//recursive procedure to find the path
{
    if(vertex == -1)
        return;
    find_path(parent[vertex]);
    for(map<string,int>::iterator it=vec.begin(); it!=vec.end(); it++)
    {
        if(it->second == vertex)
        {
            output.push_back(it->first);
            break;
        }
    }
    //printf("%d ", vertex);
}

int main()
{
    int edges, flag = 0;
    string c1,c2;
    int origen, destino;
    while(scanf("%d", &edges) != EOF)
    {
        readEdges(edges);
        setId();
        read_graph();
        cin>>c1>>c2;

        if(!flag)
           flag = 1;
        else
            printf("*\n");

        map<string,int>::iterator iter1, iter2;
        iter1 = vec.find(c1);
        iter2 = vec.find(c2);

        if(iter1 == vec.end() || iter2 == vec.end())
           printf("No route\n");
        else
        {
            origen  = vec[c1];
            destino = vec[c2];
            bfs(origen);
            if(distances[destino] == -1)
               printf("No route\n");
            else
            {
                find_path(destino);                for(int x=0; x<output.size(); x++)
                {
                    if(x == 0)
                       cout<<output[x]<<" ";
                    else if(x == output.size()-1)
                        cout<<output[x]<<endl;
                    else
                        cout<<output[x]<<endl<<output[x]<<" ";
                }
            }
        }
        clearGraph();
    }
return 0;
}

11483 – Code Creator 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=2478

Ad hoc, Output formatting.

How I did it

• Read the number of lines of the case.
• Read the strings and save it into a vector. (vec)
• Print the static header.
• Traverse vec and parse the data.
• Print the static footer.

Hints

• Careful with ‘\\’                ‘\”                ‘\”‘

Input

1
\Y

3

(empty line)

(empty line)

(empty line)

Output

Case 1:
#include<string.h>
#include<stdio.h>
int main()
{
printf(“\\Y\n”);
printf(“\n”);
return 0;
}

Case 2:
#include<string.h>
#include<stdio.h>
int main()
{
printf(“\n”);
printf(“\n”);
printf(“\n”);
return 0;
}

Code

#include <iostream>
#include <cctype>
#include <cstdio>
#include <vector>
using namespace std;
int  caso = 1;
void printHeader()
{
    printf("Case %d:\n", caso++);
    printf("#include<string.h>\n");
    printf("#include<stdio.h>\n");
    printf("int main()\n");
    printf("{\n");
}

void printInput(string str)
{
    printf("printf(\"");
    for(int c=0; c<str.size(); c++)
    {
        if(isalnum(str[c]) || isspace(str[c]))
          printf("%c",str[c]);
        else if(str[c] == '\"')
                printf("\\\"");
        else if(str[c] == '\'')
                printf("\\\'");
        else if(str[c] == '\\')
                printf("\\\\");
    }
    printf("\\n\");\n");
}

void printFooter()
{
    printf("printf(\"\\n\");\n");
    printf("return 0;\n");
    printf("}\n");
}

int main()
{
int lines;
string str;

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

    vector<string> vec;
    getline(cin,str);
    for(int a=0; a<lines; a++)
    {
        getline(cin, str);
        vec.push_back(str);
    }
    printHeader();    for(int x=0; x<vec.size(); x++)
        printInput(vec[x]);
    printFooter();
}
return 0;
}