[Google CodeJam] Qualification Round Africa 2010 – Reverse Words

Les dejo la solución de un problema que no era muy complicado (http://code.google.com/codejam/contest/351101/dashboard#s=p1), pero me costó porque nunca había tenido que solucionar un algoritmo que tuviera que leer una frase (con espacios entre cada palabra) en C++, ya que si usamos el típico “std::cin>>frase”, se lee hasta el primer espacio. La solución fue usar la sentencia “getline(cin,frase)”, a la cual se le puede agregar un tercer parámetro indicando hasta que carácter leer (por ejemplo le puedo decir que lea hasta el primer guion bajo), si se omite, se leerá hasta el primer salto de linea (caracter ‘\n’).

El algoritmo básicamente lee la frase entregada desde el final hasta el primer espacio. Por cada espacio que encuentre, imprimirá lo leído hasta el momento. Es un algoritmo eficiente, o al menos eso supongo, ya que resolvió la entrada “larga” a tiempo.

Nota1: Para cambiar el fichero de entrada, se debe cambiar el primer parámetro en la línea que dice ” freopen(“B-large-practice.in”,”r”,stdin)”, poniendo el nombre del fichero de entrada deseado.

Nota2: El programa genera un fichero de salida llamado “out.out” con la salida formateada correspondiente.

#include <iostream>
#include<cstdio>

using namespace std;

void substring(string word, int start, int end, int spaces)
{
    string substring = "";
    for(int i=start;i<=end;i++)
        cout << word[i];
    if(spaces)
    cout << " ";
}

void reverse(string word)
{
    string reversedWord = "";
    unsigned int end = word.length();
    for(int i=word.length();i>=0;i--)
    {
        if(word[i]==' ')
        {
            substring(word,i+1,end-1,1);
            end = i;
        }
    }
    substring(word,0,end-1,0);
}

int main()
{
    int N;
    string word;
    freopen("B-large-practice.in","r",stdin);
    freopen("out.out","w",stdout);
    cin >> N;
    getline(cin,word);
    int i=1;
    while(N--)
    {
        getline(cin,word);
        cout << "Case #" << i++ << ": ";
        reverse(word);
        cout << endl;
    }
    return 0;
}

Anuncios