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