11687 – Digits UVA Solution

This is an easy problem from uva judge https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2734

Brute force.

How I did it

• I read the input until I get END.
• Init a counter with 1.
• The next number is the number of digits of the input.
• If both numbers are equal I return the counter.
• Otherwise call my method again increasing the counter, and sending the new number(number of digits of the parameter number).
• I print the answer.
• Accepted!!

Hints

• The description is horrible.
• The problem is asking to generate a new number that is the number of digits of the previous one and stop when the length and the new number are equal.

Code

/*
*Author: Fabian Calsina
*Date: 3/5/2018
*/
#include <bits/stdc++.h>
using namespace std;

int getMinimum(int i, string number){

    stringstream ss;
    int digits = number.size();

    ss<< digits;

    if(ss.str() == number)
        return i;

    return getMinimum(++i, ss.str());
}

int main(){

    string input;
    int answer;

    while(cin>>input){
        if(input == "END")
            break;

        answer = getMinimum(1, input);
        printf("%d\n", answer);
    }

    return 0;
}

 

11956 – Brainfuck UVA Solution

This is an easy problem from uva judge https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3107

Brute force, parse int to hexadecimal.

How I did it

• I read the number of cases.
• I read the instruction, clean the output vector and set an index to 0;
• I iterate the instruction and follow the the instructions to “<>.+-“.
• I print the answer.
• Accepted!!

Hints

• Keep in mind this sentence from the problem: “display has an array of 100 bytes of circular memory (initialized with zeros) and a pointer to this
  array (initialized to point to the leftmost byte of the array).”.
• Keep in mind: “Individual bytes are circular as well, so increasing a 255 gives a 0 and vice versa.”.

Critical Input

1

..++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++…

Critical Output

Case 1: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

Code

/*
*Author: Fabian Calsina
*Date: 1/8/2016
*/
#include <bits/stdc++.h>
using namespace std;

vector<int>output(110);

int main(){
    int index;
    int cases;
    string instruction;
    char option;
    scanf("%d", &cases);

    for(int x=1; x<=cases; x++){
        cin>>instruction;
        fill(output.begin(), output.end(), 0);
        index = 0;

        for(int y=0; y<instruction.size(); y++){
            option = instruction[y];

            if(option == '>'){
                index++;

                if(index >= 100)
                    index = 0;
            }
            else if(option == '<'){
                index--;

                if(index <=-1)
                    index = 99;
            }
            else if(option == '+'){
                output[index]++;

                if(output[index] > 255)
                    output[index] = 0;
            }

            else if(option == '-'){
                output[index]--;
                if(output[index] < 0)
                    output[index] = 255;
            }
            else if(option == '.')
                continue;
        }

        printf("Case %d: ", x);

        for(int z=0; z<100; z++){
            if(z<99)
                printf("%02X ", output[z]);
            else
                printf("%02X\n", output[z]);
        }
    }
return 0;
}

725 – Division UVA Solution

This is an easy problem from uva judge https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=666

Complete search, brute force, pruning.

How I did it

• I read N until I get 0.
• With this formula abcde / fghij = N, I traverse from 01234 to 98765, I set fghij with these values and compute abcde = N * fghij;
• If abcde is greater than 98765 I break the loop. No more operations required.
• I check if abcde and fghij have the digits 0123456789.
• I print the answer.
• Accepted!!

Hints

• The bounds are 01234 to 98765.
• If abcde is greater than 98765 I break the loop. Otherwise TLE.
• I print a blank line between the cases.(The last case does not need the blank line).

Code

/*
*Author: Fabian Calsina
*Date: 25/12/2016
*/
#include <bits/stdc++.h>
using namespace std;

bool checkValues(int a, int b){
   map<int,int> data;

   while(a != 0){
        data[a%10]++;
        a/=10;
   }

   while(b != 0){
        data[b%10]++;
        b/=10;
   }

   if(data.size() != 10)
        return false;

   for(map<int,int>::iterator it = data.begin(); it != data.end(); it++){
        if(it->second != 1)
            return false;
   }

   return true;
}

int main(){
    int abcde, fghij, N, flagOne, flagTwo;
    bool hasAnswer, spaceAnswer = false;

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

        if(!spaceAnswer)
            spaceAnswer = true;
        else
            printf("\n");

        hasAnswer = false;

        for(fghij=1234; fghij<=98765; fghij++){
            abcde = N * fghij;
            if(abcde > 98765)
                break;
            if(abcde < 10000)
                flagOne = abcde * 10;
            else
                flagOne = abcde;
            if(fghij < 10000)
                flagTwo = fghij * 10;
            else
                flagTwo = fghij;

            if(checkValues(flagOne, flagTwo)){
                if(abcde < 10000)
                    printf("0%d / %d = %d\n", abcde, fghij, N);
                else if(fghij < 10000)
                    printf("%d / 0%d = %d\n", abcde, fghij, N);
                else
                    printf("%d / %d = %d\n", abcde, fghij, N);
                hasAnswer = true;
            }

        }

        if(!hasAnswer)
            printf("There are no solutions for %d.\n", N);
    }
return 0;
}

13012 – Identifying tea UVA Solution

This a is an easy problem from uva judge https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4900

• Just compare the tea Id with the 5 inputs.

Hints

• Read until EOF.

Code

/*
*Author: Fabian Calsina
*Date: 25/12/2016
*/
#include<stdio.h>

int main(){

    int x, teaType, input, answer;

    while( scanf("%d", &teaType) != EOF ){
        answer = 0;
        for( x=0; x<5; x++ ){
            scanf("%d", &input);
            if(input == teaType)
                answer++;
        }

        printf("%d\n", answer);
    }
return 0;
}

10895 – Matrix Transpose UVA Solution

This a is tedious but easy problem from uva judge https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1836

• I read the number of rows and columns from the matrix(rows, cols).
• I initialize two graphs. vec with the numbers of rows equal to “rows” and adj with the number if rows equal to “cols”.
• I save each matrix row input into 2 vectors.
• I build the graph with this structure vector<vector<pair<int,int> > >. pair<int,int> is column number and value of the cell.
• I transpose traversing the vec graph and I save the result in adj graph.
• I print the answer.
• Accepted!

Hints

• It’s necessary to save the column number and cell value.

Code

/*
*Author: Fabian Calsina
*Date: 25/11/2016
*/
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;

vector<vector <ii> > vec;
vector<vector <ii> > adj;

void setRow(vi vIndex, vi vValue, int rowIndex){

    //pair<int,int> = (column, value)
    pair<int,int> tmp;

    for(int x=0; x<vIndex.size(); x++){
        tmp.first  = vIndex[x];
        tmp.second = vValue[x];
        vec[rowIndex].push_back(tmp);
    }
}

void printAnswer(int rows, int cols){

    vector<ii> answerRow;
    printf("%d %d\n", cols, rows);

    for(int a=0; a<adj.size(); a++){
        answerRow = adj[a];

        if(!answerRow.size()){
            printf("0\n\n");
        }
        else{
            printf("%d", answerRow.size());
            //pair<int,int> = (column, value)
            for(int c=0; c<answerRow.size(); c++){
                printf(" %d", answerRow[c].first + 1);
            }
            printf("\n");
            //pair<int,int> = (column, value)
            for(int d=0; d<answerRow.size(); d++){
                if(d < answerRow.size()-1)
                    printf("%d ", answerRow[d].second);
                else
                    printf("%d\n", answerRow[d].second);
            }
        }
    }
}

int main(){
    int rows, cols, noEmpty, val;
    vi vIndex, vValue;
    ii tmp, tmpA;
    string trash;

    while(scanf("%d %d", &rows, &cols) != EOF){
        vec.assign(rows, vector<ii>());
        adj.assign(cols, vector<ii>());

        for(int a=0; a<rows; a++){
            scanf("%d", &noEmpty);
            if(!noEmpty){
                getline(cin, trash);
                continue;
            }
            //Read indexes
            for(int b=0; b<noEmpty; b++){
                cin>>val;
                vIndex.push_back(val-1);
            }
            //Red values
            for(int b=0; b<noEmpty; b++){
                cin>>val;
                vValue.push_back(val);
            }
            //Set graph
            //a Is the row of the graph
            setRow(vIndex, vValue, a);
            vIndex.clear();
            vValue.clear();
        }

        for(int x=0; x<vec.size(); x++){
            for(int y=0; y<vec[x].size(); y++){
                tmp = vec[x][y];
                tmpA.first = x;
                tmpA.second = tmp.second;
                adj[tmp.first].push_back(tmpA);
            }
        }
        printAnswer(rows,cols);
    }
return 0;
}

486 – English-Number Translator Solution

This is a problem from uva judge https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=427

• I read the input as a string using getline.
• I send the input to a stringstream.
• I traverse the stringstream and parse all the words.
• If the word is “hundred” or a number less than one hundred I store the result in a temporal number,  otherwise I multiply the answer, add the temporal number and set the temporal value to zero.
• Accepted!

Hints

• It’s necessary to store a temporal for small numbers.
• It’s necessary to pay attention to the words hundred and thousand.

Code

/*
*Author: Fabian Calsina
*Date: 24/11/2016
*/
#include <bits/stdc++.h>
using namespace std;

map<string, int> numbers;

void generateN(){
    numbers["zero"] = 0;
    numbers["one"] = 1;
    numbers["two"] = 2;
    numbers["three"] = 3;
    numbers["four"] = 4;
    numbers["five"] = 5;
    numbers["six"] = 6;
    numbers["seven"] = 7;
    numbers["eight"] = 8;
    numbers["nine"] = 9;
    numbers["ten"] = 10;
    numbers["eleven"] = 11;
    numbers["twelve"] = 12;
    numbers["thirteen"] = 13;
    numbers["fourteen"] = 14;
    numbers["fifteen"] = 15;
    numbers["sixteen"] = 16;
    numbers["seventeen"] = 17;
    numbers["eighteen"] = 18;
    numbers["nineteen"] = 19;
    numbers["twenty"] = 20;
    numbers["thirty"] = 30;
    numbers["forty"] = 40;
    numbers["fifty"] = 50;
    numbers["sixty"] = 60;
    numbers["seventy"] = 70;
    numbers["eighty"] = 80;
    numbers["ninety"] = 90;
    numbers["hundred"] = 100;
    numbers["thousand"] = 1000;
    numbers["million"] = 1000000;
}

int main(){
    int answer, tmp;
    string word, str;
    bool isNegative;
    generateN();

    while(getline(cin, str)){
        answer = tmp = 0;
        isNegative = false;
        stringstream ss(str);

        while (ss >> word){
            if(word == "negative")
                isNegative = true;
            else if(word == "million"){
                answer =  answer + tmp * numbers[word];
                tmp = 0;
            }
            else if(word == "thousand"){
                answer =  answer + tmp * numbers[word];
                tmp = 0;
            }
            else if(word == "hundred"){
                tmp *= numbers[word];
            }
            else{
                tmp += numbers[word];
            }
        }

        if(tmp != 0)
            answer =  answer + tmp;
        if(isNegative)
            answer *= -1;
        printf("%d\n", answer);
    }

return 0;
}

12582 – Wedding of Sultan UVA Solution

This is an easy problem from uva judge https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4027

• I read the number of cases.
• Read the string.
• I traverse the string and I trace the current node with a stack. If the current element is  in the top of the stack I pop that element otherwise I put the edge in the graph. After that I put the current element in the stack.
• For the answer I traverse my map and print the key a value size.
• Accepted!

Hints

• I’m building the graph using map<char, set<char> > graph.
• I trace the node to build the graph using a stack.

Code

/*
*Author: Fabian Calsina
*Date: 4/7/2016
*/
#include <iostream>
#include <cstdio>
#include <stack>
#include <map>
#include <set>

using namespace std;

map<char, set<char> > graph;
stack<char> currentNode;

void cleanData()
{
    while(currentNode.size())
        currentNode.pop();

    graph.clear();
}

int main()
{
    string str;
    int casos;
    char tmp;

    scanf("%d", &casos);

    for(int i=1; i<=casos; i++)
    {
        cin>>str;

        for(int x=0; x<str.size(); x++)
        {
            if(x-1 < 0)
            {
                currentNode.push(str[x]);
                continue;
            }


            if(currentNode.top() == str[x])
                currentNode.pop();
            else
            {
                tmp = currentNode.top();
                graph[tmp].insert(str[x]);
                graph[str[x]].insert(tmp);

                currentNode.push(str[x]);
            }
        }

        printf("Case %d\n", i);

        for(map<char, set<char> >::iterator iter =  graph.begin(); iter != graph.end(); iter++)
        {
            printf("%c = %d\n", iter->first, iter->second.size());
        }

        cleanData();
    }
return 0;
}

10035 – Primary Arithmetic Solution

This is an easy problem from uva judge https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=976

• I read the input until I find a 0 0.
• Set a carry variable with 0 at the beginning.
• I divide both number with 10 and I get the module 10 until both numbers are 0.
• In each division I get the last digit of the numbers dividing by 10. I add both last digits and a carry variable. If the value is greater than 9 I set the carry variable with a value different than 0, otherwise I set carry to 0.
• if the carry is greater than 0 I increase the the answer by 1 .
• Print the answer.
• Accepted!

Hints.

• Check all the carries.

Critical Input

999 1
1 999
1 989
989 1
5 5

Critical Output

3 carry operations.
3 carry operations.
1 carry operation.
1 carry operation.
1 carry operation.

Code

/*
*Author: Fabian Calsina
*Date: 30/06/2016
*/

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int carry;
    int a,b, ans;

    while(scanf("%d %d", &a, &b))
    {
        if(!a && !b) break;
        ans = 0;


        carry = 0;
        while(1)
        {
            int tmpA = a%10;
            int tmpB = b%10;

            if(tmpA + tmpB + carry >= 10 )
            {
                carry = (tmpA + tmpB + carry)/10;
            }
            else
                carry = 0;

            if(carry) ans++;
            a/=10;
            b/=10;

            //if(carry == 1)
              //  ans++;
            if(a == 0 && b == 0)
                break;
        }

        if(ans == 0)
            printf("No carry operation.\n");
        else if(ans == 1)
            printf("1 carry operation.\n");
        else
            printf("%d carry operations.\n", ans);

    }
return 0;
}

10055 – Hashmat the Brave Warrior Solution

This is an easy problem from uva judge https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=996

How I did it

• I read the input until I find EOF.
• Print the absolute value of the substraction.
• Accepted!

Hints.

• Don´t use int.

Code

/*
*Author: Fabian Calsina
*Date: 30/06/2016
*/

#include <bits/stdc++.h>

using namespace std;

int main()
{
    long a, b;

    while(scanf("%ld %ld", &a, &b) != EOF)

        printf("%ld\n", abs(a-b));

return 0;
}

644 – Immediate Decodability UVA solution

This is an easy problem from uva judge https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=585

How I did it

• I read the input as string until I find a ‘9’. If the input is diferent than ‘9’ I save the input in a vector.
• I sort the vector using the length of the strings in a non decreasing way.
• With 2 nested loops traverse the array and compare the strings.
• If I found the prefix i set a boolean variable as true.
• Print the answer.
• Accepted! 😀

Hints.

• Sort the string is really useful for compare the strings.

Code

#include <bits/stdc++.h>

using namespace std;

vector<string>vec;
bool ans;

bool cmp(string a, string b)
{
    return a.size() < b.size();
}

bool isPrefix(string toSearch, string target)
{
    for(int i=0; i<toSearch.size(); i++)
    {
        if(toSearch[i] != target[i])
            return false;
    }
    return true;
}

int main()
{
    int gL = 1;
    string toSearch, target;
    string str;
    while(cin>>str)
    {
        if(str == "9")
        {
            ans = false;
            sort(vec.begin(), vec.end(), cmp);
            //Clean vec

            for(int x=0; x<vec.size() && !ans; x++)
            {
                for(int y=x+1; y<vec.size() && !ans; y++)
                {
                    toSearch = vec[x], target = vec[y];
                    if(isPrefix(toSearch, target))
                    {
                        ans = true;
                        break;
                    }
                }
            }

            if(ans)
                printf("Set %d is not immediately decodable\n", gL++);
            else
                printf("Set %d is immediately decodable\n", gL++);

            vec.clear();
        }
        else
        {
            vec.push_back(str);
        }
    }
return 0;
}