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

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

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