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

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

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

Word Length and Frequency 10293

This is an easy problem from uva judge http://uva.onlinejudge.org/external/102/10293.html

Ad hoc problem.

How I did it

• Read line by line the strings while the first character of the string is diferent to # .
• Iterate throught the string searching the characters that are alphabetics and saving the length of the current word.
• If I find a space separator character (” ” ,? ,! ,. ,’,’) I save the current length of a word in a map<int, int> where the key is the size of the word and the value the number of word with the size of the key. Reset the word size variable.
• If I find the # character as first character of a line, we print the map content.
• Clean map, clear flag variables and print a blank line.

Hints

• The input is small, a brute force aproach is enough.
• The length of the word is only composed by alphabetic characters.
• Consider this type of case as only a word:  you’ve  length = 5.
• The space separators are: ” “, ?, !, ., , .
• Print a blank line after each block.
• And end block could be : #this is the end of block

Code

#include <iostream>
#include <cstdio>
#include <map>
#include <cctype>
using namespace std;
int main()
{
string cad;
map<int,int> myMap;
int wSize = 0;
while(getline(cin,cad))
{
    if(cad[0] != '#')
    {
        for(int a=0; a<cad.size(); a++)
        {
            if(isalpha(cad[a]))
               wSize++;
            else if(isspace(cad[a]) || cad[a] == '!' || cad[a] == '?' || cad[a] == ',' || cad[a] == '.')
            {
                myMap[wSize]++;
                wSize = 0;
            }
        }
        if(cad[cad.size()-1] != '-' && wSize>0)
        {
            myMap[wSize]++;
            wSize = 0;
        }
    }
    else
    {   map<int,int>::iterator it = myMap.begin();
        if(it->first == 0)
            it++;
        for(it = it; it!= myMap.end(); it++)
            printf("%d %d\n",it->first,it->second);
        printf("\n");
        wSize = 0;
        myMap.clear();
    }
}
return 0;
}

Uva 10126 – Zipf’s Law

This is an easy problem in Uva judge.

http://uva.onlinejudge.org/external/101/10126.html

How I did it:

• Get n. (Number of occurrences that the problem asks validate)
• I read line per line
• I get the words from the read line
• Put the words int a stl map<string,int>
• Iterate in the map and if the int is equal to n , print the word.
• If no word appears n times print “There is no such word.”

Hints:

• Print a blank line between  cases. The last case doesn’t have a blank line.
• If no word appears n times print “There is no such word.”
• The words must be sorted.

Code:

In my github : https://github.com/Fabho/algorithmsSolved/blob/master/10126.cpp

#include <iostream>
#include <cstdio>
#include <cctype>
#include <map>
using namespace std;
map<string,int> myMap;

void getWords(string cad){
string tmp = "";

for(int x=0; x<cad.size(); x++)
   {
     if(isalpha(cad[x]))
        tmp+=tolower(cad[x]);
     else{
           if(tmp.size() > 0)
           {
             myMap[tmp]++;
             tmp = "";
           }

         }

   }
 if(tmp.size() > 0)
    myMap[tmp]++;
 tmp = "";
}

int main(){
int n, casos = 0;
string cad;

while(scanf("%d",&n) != EOF){
    getline(cin,cad);//trash
    while(getline(cin,cad)){
    if(cad == "EndOfText")
       break;
    getWords(cad);
    }
    bool flag = false;

    if(casos == 0)
       casos = 1;
    else
        printf("\n");
    for(map<string,int>::iterator it = myMap.begin(); it != myMap.end(); it++)
    {
        if(it->second == n)
           {
            printf("%s\n", it->first.c_str());
            flag = true;
           }
    }
    if(flag == false)
       printf("There is no such word.\n");
    myMap.clear();
}
return 0;
}