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

459 – Graph Connectivity 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=400

Graphs, graph traversal, dfs, connected components.

How I did it

• I read the number of cases.
• I read the number of vertices.(Max 26 vertices)
• I read the edges until I found an empty line. and set the union of the graph.
• Traverse all the not visited vertexs and call dfs(node not visited yet). Increment the number of connected component in every call to dfs.
• Print the number of connected components.

Hints

• The maximum number of nodes is 26. (From A to Z).
• The graph always will be numered from 0 to 26   0<=nodes<27
• I play with the ASCII value for get the node value. i.e ‘A’ – 65 = 0, ‘B’ – 65 = 1, ‘C’ – 65 = 2…. and so on.
• Print a blank line between cases. The last case does not need the blank line.

Code

#include <iostream>
#include <cstdio>
#include <vector>
#define  DFS_WHITE -1
#define  DFS_BLACK 1
using namespace std;
typedef vector<int> vi;

vector<vi> graph;
vi dfs_num;

void readGraph()
{
    string edge;
    int node1, node2;
    getline(cin, edge);

    while(getline(cin,edge))
    {
        if(edge.size() == 0)
           break;
        node1 = edge[0] - 65;
        node2 = edge[1] - 65;
        graph[node1].push_back(node2);
        graph[node2].push_back(node1);
    }
}

void print()
{
    for(int x=0; x<graph.size(); x++)
    {cout<<"Nodo : "<<x<<endl;
        for(int y=0; y<graph[x].size(); y++)
            cout<<graph[x][y]<<" ";
        cout<<endl;
    }
}

void dfs(int node)
{
    dfs_num[node] = DFS_BLACK;
    for(int c=0; c<graph[node].size(); c++)
        if(dfs_num[graph[node][c]] == DFS_WHITE)
          dfs(graph[node][c]);
}

int main()
{
string nodes;
int casos, CC, flag=0;
scanf("%d", &casos);
for(int x=0; x<casos; x++)
{
    cin>>nodes;
    graph.assign(nodes[0] - 64, vi());
    dfs_num.assign(nodes[0] - 64, DFS_WHITE);
    readGraph();
    //print();
    CC = 0;
    for(int z=0; z<dfs_num.size(); z++)
    {
        if(dfs_num[z] == DFS_WHITE)
        {
            dfs(z);
            CC++;
        }
    }
    if(flag == 0)
       flag++;
    else
        printf("\n");
    printf("%d\n", CC);
}
return 0;
}

260 – Il Gioco dell’X 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=196

Graphs, graph traversal, dfs, flood fill.

How I did it

• Read the size of the row.
• Read the graph.
• Init dfs_matriz. If an element is equal to be set the value to -1, otherwise 0.
• Traverse dfs_matriz. If an element is equal to -1 call dfs(row, col).
• In the dfs execution. If a cell has -1(not discovered) insert the row into a set.
• When dfs ends, check if the row size is equal to set size. If yes break the loop and set a flag = true(Black wins), otherwise continue with the search.
• Print the result.

Hints

• Always you will have a winner. (The problem description has not another option).

Code

#include <iostream>
#include <cstdio>
#include <set>
#define  DFS_WHITE -1
#define  DFS_BLACK 1
#define  NODES     202
using namespace std;
int  dfs_matriz[NODES][NODES];
char matriz[NODES][NODES];
set<int> mySet;
int  row;

void dfs(int x, int y)
{
    dfs_matriz[x][y] = DFS_BLACK;
    mySet.insert(x);

    int a=x, b=y;
            if(a-1 >= 0)
            {
                if(dfs_matriz[a-1][b] == DFS_WHITE)
                    dfs(a-1, b);
                if(b-1 >= 0 && dfs_matriz[a-1][b-1] == DFS_WHITE)
                    dfs(a-1, b-1);
            }
            if(a+1 < row)
            {
                if(b+1 < row && dfs_matriz[a+1][b+1] == DFS_WHITE)
                    dfs(a+1, b+1);
                if(dfs_matriz[a+1][b] == DFS_WHITE)
                    dfs(a+1, b);
            }
            if(b-1 >= 0 && dfs_matriz[a][b-1] == DFS_WHITE)
                dfs(a,b-1);
            if(b+1 < row && dfs_matriz[a][b+1] == DFS_WHITE)
                dfs(a,b+1);
}

void readGraph(int tam)
{
    string str, data = "";

    for(int x=0; x<tam; x++)
    {
        cin>>str;
        data += str;
    }
    int index = 0;
    for(int x=0; x<row; x++)
        for(int y=0; y<row; y++, index++)
            matriz[x][y] = data[index];
}

void initGraph(char pawn)
{
    for(int x=0; x<row; x++)
        for(int y=0; y<row; y++)
        {
            if(matriz[x][y] == pawn)
               dfs_matriz[x][y] = DFS_WHITE;
            else
                dfs_matriz[x][y] = 0;
        }
}

int main()
{
int casos = 1;
while(scanf("%d", &row))
{
    if(!row)
       break;
    readGraph(row);    bool flag = false;
    initGraph('b');
    for(int a=0; a<row && flag == false; a++)
        for(int b=0; b<row; b++)
        {
            if(dfs_matriz[a][b] == DFS_WHITE)
            {
                mySet.clear();
                dfs(a,b);
                if(mySet.size() == row)
                {
                    flag = true;
                    break;
                }
            }
        }
    if(flag)
       printf("%d B\n", casos++);
    else
        printf("%d W\n", casos++);
}
return 0;
}

280 – Vertex 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=216

Graphs, graph traversal, dfs, bfs.

How I did it

• Read the number of nodes. (If a node is equal to 0 stop de program).
• Read the edges and set the graph until I find a node equal to 0.
• Read the number of queries.
• Read the node to search.
• Call dfs(node to search).
• Count the vertex not visited.
• Print the answer.

Hints

• It’s posible to use an Adjacency matrix, adjacency list.
• You can use dfs, bfs to traverse the graph.
• Though you would generally mark the starting node as visited, make sure you don’t in this case. The starting node is only visited if there’s some loop that brings you back to the starting node.
• The graph could not have edges.

Critical input

1
1 1 0
0
1 1
1
0
1 1
0

Critical output

0
1 1

Code

#include <iostream>
#include <cstdio>
#include <vector>
#define  DFS_WHITE -1
#define  DFS_BLACK 1
using namespace std;
typedef vector<int> vi;

vector<vi> graph;
vi dfs_num;

void readGraph()
{
    int node, next;

    while(scanf("%d", &node))
    {
        if(!node)
           break;
        while(scanf("%d", &next))
        {
            if(!next)
               break;
            graph[node-1].push_back(next-1);
        }
    }
}

void dfs(int node)
{
    int current;
    for(int x=0; x<graph[node].size(); x++)
    {
        current = graph[node][x];
        if(dfs_num[current] ==DFS_WHITE)
        {
            dfs_num[current] = DFS_BLACK;
            dfs(current);
        }
    }
}

void print()
{
    int notReach = 0;
    vector<int> out;
    for(int x=0; x<dfs_num.size(); x++)
        if(dfs_num[x] == DFS_WHITE)
        {
            notReach++;
            out.push_back(x+1);
        }
    if(notReach == 0)
       printf("0\n");
    else
        printf("%d ", notReach);
    for(int x=0; x<out.size(); x++)
    {
        if(x==out.size() - 1)
           printf("%d\n", out[x]);
        else
            printf("%d*", out[x]);
    }
}

int main()
{
int nodes, queries,sNode;
while(scanf("%d", &nodes) != EOF)
{
    if(!nodes)
       break;
    graph.assign(nodes, vi());
    readGraph();    scanf("%d", &queries);
    for(int x=0; x<queries; x++)
    {
        dfs_num.assign(nodes, DFS_WHITE);
        scanf("%d", &sNode);
        dfs(sNode-1);
        print();
    }
}
return 0;
}

11900 – Boiled Eggs 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=3051

Greedy , Adhoc..

How I did it

• Read the number of cases.
• For each case read the number of eggs, max eggs that the bowl support, and max weight that bowl support.
• Read the weight of the eggs and push it inside a vector.
• Init tot and totW to zero. // If tot >= eggs or totW > max bowl weight I break the loop.
• Traverse the vector until  tot <  eggs && totW < max bowl weight. Increment tot, and totW.
• Print the answer.

Hints

• The weight of the eggs is already sorted.
• The input is really small.

Code

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int main()
{
int casos, eggs, maxEggs, maxWeight, val;
int tot, totW;
scanf("%d", &casos);
for(int a=1; a<=casos; a++)
{
    vector<int> vec;
    scanf("%d %d %d", &eggs, &maxEggs, &maxWeight);
    for(int b=0; b<eggs; b++)
    {
        scanf("%d", &val);
        vec.push_back(val);
    }

    tot = totW = 0;
    for(int x=0; x<vec.size(); x++)
    {
        totW += vec[x];
        if(totW > maxWeight)
           break;
        else if( tot < maxEggs)
                tot++;
        else
            break;
    }
    printf("Case %d: %d\n", a, tot);
}
return 0;
}

11356 – Dates 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=2341

Adhoc. I solve this problem using Java GregorianCalendar class.

How I did it

• Read the number of cases.
• Init an array of months.
• Read the date to process.
• Read the days to add.
• Init a GregorianCalendar object with the day, month and year of the input.
• Add the days to the GregorianCalendar object.
• Print the answer

Hints

• Gregorian Calendar manage the month in this way. January = 0, February = 1 and so on.
• Gregorian Calendar manage the leap year. I do not care how it does, but it does.
• Careful with days less than 10 in the output, Check the output example

Code

import java.util.*;
public class Dates11356 {

	public static void main(String[]args)
	{	
		String[] monthArray = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"};

		String currentDate;
		String[] dateParts;
		int casos, cDay, cMonth=0, cYear, traverseDays;

		Scanner lee = new Scanner(System.in);
		casos = lee.nextInt();

		for(int a=1; a<=casos; a++)
		{
			currentDate = lee.next();
			traverseDays = lee.nextInt();

			dateParts = currentDate.split("-");
			cDay = Integer.parseInt(dateParts[2]);
			cYear = Integer.parseInt(dateParts[0]);
			for(int x=0; x<12; x++)
				if(monthArray[x].equals(dateParts[1]))
				{
					cMonth = x;
					break;
				} 	

			Calendar myCalendar = new GregorianCalendar(cYear, cMonth, cDay);
			myCalendar.add(Calendar.DATE , traverseDays);

			int year = myCalendar.get(Calendar.YEAR);
			int day  = myCalendar.get(Calendar.DATE);
			String month = monthArray[myCalendar.get(Calendar.MONTH)];
			//Case 1: 1985-January-01
			//System.out.printf("Case %d: %d-%s-%02d\n", a, year, month, day);//Formatear Para que tenga un 0 por delante if dia <10
			System.out.print("Case " + a + ": " + year + "-" + month + "-");
			if(day<10)
			  System.out.println("0" + day);
			else
				System.out.println(day);
		}
	}
}

10196 – Check The Check 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=1137

Adhoc.

How I did it

• Read the chess board configuration and save the black and white king row and col in global variables.
• First, I check if the black king is under attack and print the black king is under attack. Otherwise I check if the white king is under attack and print the white king is under attack, otherwise print no king is under attack.

Hints

• The input is really small, so a complete search approach is enough. (My algorithm 0.16 sec).
• The queen has the same movement as bishop and rock.
• A king is under attack of a bishop  if: abs(kingRow – otherPieceRow) – abs(kingCol – otherPieceCol) == 0.

Code

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstdlib>
using namespace std;
int rowBlack, colBlack, rowWhite, colWhite;
char chessBoard[9][9];

bool readGame()
{
string tmp, myStr = "";
int index = 0;
    for(int a=0; a<8; a++)
    {
        cin>>tmp;
        myStr += tmp;
    }

    bool flag = false;
    for(int x=0; x<8; x++)
        for(int y=0; y<8; y++, index++)
        {
            chessBoard[x][y] = myStr[index];
            if(myStr[index] != '.')
               flag = true;
            if(chessBoard[x][y] == 'k')
            {
                rowBlack = x;
                colBlack = y;
            }
            if(chessBoard[x][y] == 'K')
            {
                rowWhite = x;
                colWhite = y;
            }
        }
return flag;
}

bool checkRock(int a,int b, int kRow, int kCol, char king)
{
    if(a != kRow && b != kCol)
       return false;
    for(int x=a+1; x<8; x++)
    {
        if(chessBoard[x][b] == king)
           return true;
        else if(isalpha(chessBoard[x][b]) && chessBoard[x][b] != king)
               break;
    }
    for(int x=a-1; x>=0; x--)
    {
        if(chessBoard[x][b] == king)
           return true;
        else if(isalpha(chessBoard[x][b]) && chessBoard[x][b] != king)
               break;
    }
    for(int x=b+1; x<8; x++)
    {
        if(chessBoard[a][x] == king)
           return true;
        else if(isalpha(chessBoard[a][x]) && chessBoard[a][x] != king)
               break;
    }
    for(int x=b-1; x>=0; x--)
    {
        if(chessBoard[a][x] == king)
           return true;
        else if(isalpha(chessBoard[a][x]) && chessBoard[a][x] != king)
               break;
    }
return false;
}

bool checkBishop(int x, int y, int rBlack, int cBlack, char king)
{
    if(abs(x - rBlack) - abs(y - cBlack) != 0)
       return false;

    for(int a=x-1, b=y-1;  a>=0 && b>=0; a--, b--)
    {
        if(chessBoard[a][b] == king)
           return true;
        else if(isalpha(chessBoard[a][b]) && chessBoard[a][b] != king)
                break;
    }
    for(int a=x-1, b=y+1;  a>=0 && b<8; a--, b++)
    {
        if(chessBoard[a][b] == king)
           return true;
        else if(isalpha(chessBoard[a][b]) && chessBoard[a][b] != king)
                break;
    }
    for(int a=x+1, b=y-1;  a<8 && b>=0; a++, b--)
    {
        if(chessBoard[a][b] == king)
           return true;
        else if(isalpha(chessBoard[a][b]) && chessBoard[a][b] != king)
                break;
    }
    for(int a=x+1, b=y+1;  a<8 && b<8; a++, b++)
    {
        if(chessBoard[a][b] == king)
           return true;
        else if(isalpha(chessBoard[a][b]) && chessBoard[a][b] != king)
                break;
    }
return false;
}

bool checkKnight(int x, int y, int rBlack, int cBlack, char king)
{
    if(x-2>=0 && y-1>=0 && chessBoard[x-2][y-1] == king)
       return true;
    else if(x-1>=0 && y-2>=0 && chessBoard[x-1][y-2] == king)
            return true;
    else if(x+1<8 && y-2>=0 && chessBoard[x+1][y-2] == king)
           return true;
    else if(x+2<8 && y-1>=0 && chessBoard[x+2][y-1] == king)
           return true;
    else if(x+2<8 && y+1<8 && chessBoard[x+2][y+1] == king)
           return true;
    else if(x+1<8 && y+2<8 && chessBoard[x+1][y+2] == king)
           return true;
    else if(x-1>=0 && y+2<8 && chessBoard[x-1][y+2] == king)
           return true;
    else if(x-2>=0 && y+1<8 && chessBoard[x-2][y+1] == king)
           return true;
    else
         return false;
}

bool checkPawn(int x,int y, int rowBlack, int colBlack, char king)
{
    if(x-1 >=0 && y-1 >=0 && chessBoard[x-1][y-1] == king)
        return true;
    else if(x-1 >=0 && y+1<8 && chessBoard[x-1][y+1] == king)
           return true;
    else
        return false;
}

bool checkPawnWhite(int x,int y, int rowBlack, int colBlack, char king)
{
    if(x+1<8 && y-1 >=0 && chessBoard[x+1][y-1] == king)
        return true;
    else if(x+1<8 && y+1<8 && chessBoard[x+1][y+1] == king)
           return true;
    else
        return false;
}

bool checkBlack()
{
    for(int x=0; x<8; x++)
        for(int y=0; y<8; y++)
        {
            if(chessBoard[x][y] != '.' && isupper(chessBoard[x][y]))
            {
                if(chessBoard[x][y] == 'R')
                {
                    if(checkRock(x,y, rowBlack, colBlack, 'k'))
                      return true;
                }
                else if(chessBoard[x][y] == 'B')
                {
                    if(checkBishop(x,y, rowBlack, colBlack, 'k'))
                       return true;
                }
                else if(chessBoard[x][y] == 'Q')
                {
                    if(checkRock(x,y, rowBlack, colBlack, 'k') || checkBishop(x,y, rowBlack, colBlack, 'k'))
                       return true;
                }
                else if(chessBoard[x][y] == 'N')
                {
                    if(checkKnight(x, y, rowBlack, colBlack, 'k'))
                       return true;
                }
                else if(chessBoard[x][y] == 'P')
                {
                    if(checkPawn(x,y, rowBlack, colBlack, 'k'))
                       return true;
                }
            }
        }
return false;
}

bool checkWhite()
{
    for(int x=0; x<8; x++)
        for(int y=0; y<8; y++)
        {
            if(chessBoard[x][y] != '.' && islower(chessBoard[x][y]))
            {
                if(chessBoard[x][y] == 'r')
                {
                    if(checkRock(x,y, rowWhite, colWhite, 'K'))
                      return true;
                }
                else if(chessBoard[x][y] == 'b')
                {
                    if(checkBishop(x,y, rowWhite, colWhite, 'K'))
                       return true;
                }
                else if(chessBoard[x][y] == 'q')
                {
                    if(checkRock(x,y, rowWhite, colWhite, 'K') || checkBishop(x,y, rowWhite, colWhite, 'K'))
                       return true;
                }
                else if(chessBoard[x][y] == 'n')
                {
                    if(checkKnight(x, y, rowWhite, colWhite, 'K'))
                       return true;
                }
                else if(chessBoard[x][y] == 'p')
                {
                    if(checkPawnWhite(x,y, rowWhite, colWhite, 'K'))
                       return true;
                }
            }
        }
return false;
}int main()
{
int casos = 1;
while(readGame())
{
    if(checkBlack())
       printf("Game #%d: black king is in check.\n", casos++);
    else if(checkWhite())
            printf("Game #%d: white king is in check.\n", casos++);
    else
        printf("Game #%d: no king is in check.\n", casos++);
}
return 0;
}

10919 – Prerequisites? 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=1860

Adhoc, Complete Search approach.

How I did it

• Read the number of courses and categories.
• Read all the courses and insert into a vector.
• Read all the categories. Save the total courses and minimum required.
• Set a counter in 0.
• If a course if founded inside categories vector. Increment the counter
• If the “set size”  is equal to “number of balls +1″ print Y, otherwise print N.
• At the end of the loop if counter is more or equal than minimum print yes, otherwise print no.

Hints

• All the course has 4 digits. Save this as strings. (a course is 0000, 0001, 0003).

Code

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int main()
{
int courses, categories, total, minimum;
string str;
while(scanf("%d", &courses))
{
    if(!courses)
       break;
    scanf("%d", &categories);
    vector<string>courseSelected;

    for(int x=0; x<courses; x++)
    {
        cin>>str;
        courseSelected.push_back(str);
    }
    int flag = 1;
    for(int c=1; c<=categories; c++)
    {
        scanf("%d %d", &total, &minimum);
        int tmp = 0;
        for(int x=1; x<=total; x++)
        {
            cin>>str;
            for(int y=0; y<courseSelected.size(); y++)
            {
                if(courseSelected[y] == str)
                {
                    tmp++;
                    break;
                }
            }
        }
        if(tmp<minimum)
           flag = 0;
    }
    if(!flag)
       printf("no\n");
    else
        printf("yes\n");

}
return 0;
}

12239 – Bingo! 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=3391

Adhoc, Complete Search approach.

How I did it

• Read the number of balls and the remaining balls.
• Read all the remaining balls and insert them into a vector.
• Generate all the posible cambination with two elements.(Two nested for)
• Insert in a set the absolute value of the subtraction of the two possible elements.
• If the “set size”  is equal to “number of balls +1” print Y, otherwise print N.

Hints

• We can use the same ball to generete a number. ( 5, 5 = 0).

Code

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <set>
using namespace std;
int main()
{
int number, remain, val, tmp;
while(scanf("%d %d", &number, &remain))
{
    vector<int> vec;
    set<int> mySet;
    if(!number && !remain)
       break;

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

    for(int a=0; a<vec.size(); a++)
        for(int b=0; b<vec.size(); b++)
        {
            tmp = abs(vec[a] - vec[b]);
            mySet.insert(tmp);
        }

    if(mySet.size() == number+1)
       printf("Y\n");
    else printf("N\n");
}
return 0;
}