Programacion, ACM ICPC, UVa Online Judge

Una de las partes que mas se les complica a los nuevos equipos interesados en concursos es el procesamiento de la entrada.
Muchas veces el algoritmo a utilizar es sencillo, y tienen la solución pero, no lo solucionan, debido a que la entrada es complicada de procesar.

Esta entrada va dedicada al uso de varias librerías, que nos permitirán manipular la entrada, haciendo nuestra vida mas sencilla al momento de leer.

Introducción 
Lo expuesto a continuación su implementación sera en C++ como el uso de istringstream y los mapas.
Recordar tambien agregar using namespace std; al final de donde se agregaron las librerias.
Ejemplo:
#include<stdio.h>
#include<iostream>
using namespace std;
Para los archivos en C++ hay que guardar siempre los archivos como .cpp y compilar siempre con g++.

Referente a la lectura y escritura de datos en C++, podemos hacer uso del scanf sin ningun problema, pero tambien C++ nos ofrece otras formas de leer datos.
Para la lectura de datos es recomendable agregar la libreria #include<iostream>. Con esta libreria nosotros podemos utilizar los metodos siguientes:

  • cin: Que es la lectura de datos
  • cout: Que es la escritura de datos
  • getline: Que es la lectura de un renglón

Lo que tienen las 2 primeros metodos, es que nosotros podemos tanto leer y escribir sin especificar el tipo de dato:
Ejemplo:
int x;
cin >> x;
cout << x << “\n”;

Como notaran, no especifique el tipo de dato que se esta leyendo o escribiendo, y esto se puede aplicar a cualquier tipo de dato, como int, char, float, double, string.
El cin vendría siendo como el scanf ya que busca en la entrada la forma de acomodarlo en el tipo de dato que estamos leyendo.

El uso de getline vendria siendo similar al gets. Esto se usa para leer en strings.
Ejemplo:
string cadena;
getline(cin,cadena);
cout << cadena << endl;

Al leer con el getline, hacemos lo mismo que haría un gets.
El uso de endl, es igual que colocar un salto de linea.

Hay que destacar que el uso de estos métodos es muy efectivo pero a cambio perdemos tiempo, ya que al no especificar que tipo de datos vamos a leer, el programa tiene que determinarlo y eso toma valioso tiempo, lo cual prodria provocar que nuestro programa no ejecute en el tiempo especificado.
Es recomendable no usarlo demasiado, principalmente en lo personal, solo lo ocupo para la lectura de string.

Tip 1: Borrar caracteres y utilizar flujos
Aveces nosotros tenemos en una entrada que simplemente hay que remover algún tipo de carácter, ya sean comas, paréntesis, corchetes, etc.
Un ejemplo clásico de una entrada de este estilo, es cuando nos dan coordenadas en un plano x,y.
Ejemplo:
(1,2) – (2,3) – (4,0)

Si la entrada fuera de la siguiente forma
1 2 2 3 4 0
Es mas fácil de procesar, ya que sabemos que hay que leer de 2 en 2 números para un par de coordenadas.
Esto lo podemos hacer de la siguiente manera en C++:
Utilizando string nosotros podemos leer la cadena y tendriamos algo asi:
string renglon = “(1,2) – (2,3) – (4,0)”;
De ahi, facilmente podemos quitarle los parentesis y las comas y los guiones con un ciclo for:
for(i=0;i<renglon.size();i++)
   if(!(renglon[i]>=’0′ && renglon[i]<=’9′))
       renglon[i]=’ ‘;

Lo que ponemos en la condicion seria como leer, “Cualquier cosa que no sea numero conviértelo espacio”.
De esa manera el string nos queda de la siguiente forma:
string renglon = ” 1 2     2 3     4 0 “;

Normalmente nosotros leemos todo desde teclado, o desde un archivo, pero nosotros podemos tambien hacer que el string generado, se vuelva la entrada a nuestras variables.
Esto es posible con istringstream que se encuentra en la libreria #include<sstream>
Nosotros podemos hacer lo siguiente:
istringstream entrada(renglon);
Ahora nuestro flujo se llama “entrada”. Esto no quiere decir que no podamos leer de teclado o archivos al mismo tiempo, nosotros podremos leer del flujo “entrada” en el momento que lo requiramos.

Para leer los números utilizaríamos el siguiente pedazo de código:
int x,y;
while(entrada >> x >> y){
      printf(“%d %d\n”,x,y);
      //O la manipulación que nosotros queramos hacer con las variables x,y
}

El código anterior, con la entrada anterior, genera la siguiente salida:
1 2
2 3
4 0

Como verán, pasamos de un tipo string a un tipo entero.
Esto es posible debido a que se direccionamiento el flujo.
Para que quede mas claro, es como si la cadena que ustedes generaron, la metieran por teclado.
¿Que pasa si yo meto por teclado “1__2____2___3__4____0”, donde los _ son espacios, y si lo leo con un scanf(“%d%d”,&x,&y)?
En la variable “x,y” ira obteniendo los valores correspondientes, por que el scanf omite los espacios, ya que le indicamos que sea un entero lo que tiene que leer.
Es exactamente lo mismo, ya que si nuestra cadena fuera como el ejemplo anterior y nosotros queremos guardar un entero, omite los espacios al momento de la lectura.

Los flujos no solo se restringen a procesar enteros, podemos usarlos para cualquier tipo de dato que nosotros requiramos.
Un ejemplo un poco mas completo:
(hola,1,1.3,x)

Eso podríamos leerlo con scanf de la siguiente manera:
scanf(“(%s,%d,%lf,%c)”,&cad,%ent,&dou,&car);

Otra forma, simplemente para ejemplificar el uso del istringstream es el siguiente:
string cad=”(hola,1,1.3,x)”;
for(i=0;i<cad.size();i++)
    if(cad[i]=='(‘ || cad[i]==’)’ || cad[i]==’,’)
          cad[i]=’ ‘;

Con ese pedazo de código, lo que hicimos fue quitarle paréntesis y comas a la cadena dejándola así:
string cad=” hola 1 1.3 x “;

Ahora si utilizamos un flujo sobre el string cad obtendremos lo siguiente:
string cadena;
int n;
double d;
char c;
istringstream in(cad);
//Recuerden que el nombre del flujo puede ser cualquiera

//En el caso anterior se llamaba “entrada” en este “in”
while(in >> cadena >> n >> d >> c){
      printf(“%s %d %lf %c\n”,cadena.c_str(),n,d,c);
      //O la manipulación que queramos darle a los datos
}

Con eso, nosotros ya podemos tener en variables independientes los valores que encontramos en la entrada.


Tip 2: Convertir un char a un numero

Otro problema que se puede encontrar es asignar a una letra un numero, esto se puede solucionar de manera muy rápida y sencilla.
Si nosotros tenemos la letra ‘A’ y queremos asignarle un numero, lo mas normal es que digamos ‘A’ = 0.

Para hacer esto rápidamente nosotros podemos hacer lo siguiente:
char c=’A’;
int n=c-‘A’;

Lo que tendrá la variable n es un 0.
Esto se debe a que los caracteres están en ascii, y cada carácter tiene asociado un numero.
Uno puede revisar el ascii de un carácter imprimiendo con un %d en vez de un %c.
printf(“%d\n”,c);
Así, si nosotros tenemos la siguiente entrada:
AB
BC
CD
y queremos asociarle un entero a cada letra, podemos utilizar el siguiente código:
char s[10];
scanf(“%s”,&cad);
int val1 = s[0]-‘A’;
int val2 = s[1]-‘A’;

Con eso val1 seria igual a 0 y val2 seria igual a 1.
Cabe mencionar que si las letras son minúsculas, no es lo mismo restarle una letra minúscula a una mayúscula o viceversa, ya que el código ascii asociado a la letra ‘a’ no es igual al de la letra ‘A’. Usted puede comprobar esto imprimiendo el valor en decimal.

Tip 3: Uso de Mapas
Los mapas es una de las formas mas rápidas de enmascaramiento de datos.
En un mapa nosotros podemos relacionar a una variable de cualquier tipo de dato, a otra variable de cualquier tipo de dato.
Por ejemplo:

“ACM” = 10;
10 = “ACM”
(x,y) = (a,b,c,d)

Las cosas mas importantes de los mapas son:

  1. El lado izquierdo del mapa es ÚNICO, no se puede repetir
  2. Si se le asigna del lado derecho un entero, este inicia automáticamente en 0
  3. Si el dato del lado izquierdo ya existía anteriormente en el mapa, el dato nuevo reemplaza al dato anterior.
  4. El mapa ordena automáticamente con respecto al lado izquierdo.

El lado “izquierdo” del mapa se llama llave (key) y el lado “derecho” es el valor asignado a la llave (value).
Como se observa vagamente en los ejemplos, podemos rapidamente relacionar tipos de datos diferentes.
Para el uso de un mapa, hay que utilizar la libreria #include<map>
Para declararlo, se hace de la siguiente manera:

map<TIPO1,TIPO2> nombre;

Donde TIPO1 tiene que ser un tipo de dato que se pueda “ordenar”.
Donde TIPO2 puede ser cualquier tipo de dato, ya sea nativo o un tipo de dato propio.
Cuando me refiero a que se pueda ordenar el tipo de dato, es que nosotros sepamos cual dato es menor y cual mayor.
En los tipos de datos que nos da C++ como int, double, float,string,pair,char, etc, no tenemos ese problema, ya que ya esta definido que tipo de dato es menor que otro.
Cuando nosotros definimos nuestro propio tipo de dato, como en una estructura, si pretendemos usarla en un mapa, tendremos que definir que estructura es menor, a que estructura.

Para eso, se realiza de la siguiente manera:

typedef struct e{
     //Nuestras variables aca
     bool operator <(const e &a) const{
                //Realizamos las comparaciones necesarias para indicar cual estructura es menor
     }
}estrucura;

Como notaran, solo el nombre de la estructura es “e” y lo que se encuentra de los parentesis (const e &a) es “e”. Esas 2 tienen que ser la misma.
El &a es el nombre de la variable, puede llamarse como gusten.

Un ejemplo:
Supongamos que nuestra estructura tiene una cadena y un entero, tal como el nombre de una persona y su salario.
Nosotros queremos que se ordenen por el salario. Tendríamos que hacer lo siguiente.

typedef struct p{
      string nombre;
      int salario;
      bool operator <(const p &a) const{ 
                //Realizamos las comparaciones necesarias para indicar cual estructura es menor
                // como queremos que se ordenen por el salario de menor a mayor, realizamos lo siguiente
               if(salario == a.salario)
                      return nombre < a.nombre;
               return salario < a.salario;  
     }
}persona;

En esa estructura, lo que hacemos es comparar, si tienen el mismo salario, el desempate se da por el nombre, si no, se da por que tenga menor salario.
Una vez definido eso, podemos utilizar el mapa con persona y definir cosas de este estilo:

map<persona,string> departamentos;

Ahora, para poder almacenar datos en un mapa, se realiza como si fuera un arreglo.
Ejemplo:
map<string,string> mapa;
string acm = “ACM”:
string icpc = “ICPC”;
mapa[acm]=icpc;

Ahora, cuando nosotros intentemos obtener el dato relacionado con acm obtendremos la cadena “ICPC”
Ejemplo:
cout << mapa[acm] << endl;
La linea de codigo nos imprimiria “ICPC”

Para sustituir el dato, nosotros hacemos lo siguiente
string utm=”UTM”;
mapa[acm]=utm;
Una vez hecho esto, se borro el valor anterior y ahora cuando revisemos su valor, obtendremos la cadena “UTM”.

En un mapa tambien existen varias cosas que podemos hacer y que son de igual importancia.

map.clear();
Borra el mapa y elimina todos los datos que tenia

map.size();
Nos indica cuantos elementos tiene el mapa

map.find(key);
Nos da la posición de del elemento key en el mapa.

Para utilizar esta ultimo método, hay que saber lo que es un iterador.
En los mapas, no podemos recorrerlos como un indice en un arreglo, ya que no son siempre números los que se usan, y aveces es otro tipo de datos.
El iterador lo podemos ver como un puntero hacia los datos del mapa.
Se declara de la siguiente manera:
map<TIPO1,TIPO2>::iterator it;

Donde TIPO1 y TIPO2 tienen que ser los mismos del mapa que queremos utilizar, y la variable it, es el nombre del iterador.
Al utilizar un iterador, nosotros tenemos acceso a 2 partes importantes del mapa, el principio y el fin del mapa.
Para acceder a ellas se usan los siguientes métodos.

map.begin();
Indicando donde empieza el mapa

map.end();
Indicando donde termina el mapa.

Cada uno de los 3 métodos nos regresa un iterador.

it=map.begin();
it=map.end();
it=map.find(s);

Si lo que nosotros queremos es imprimir todos los elementos del mapa, podemos utilizar el iterador para movernos a través de el y acceder a los datos que estos tiene.
Ejemplo:

for(it=mapa.begin();it!=mapa.end();it++)
     cout << (*it).first << ” ” << (*it).second << endl;

Con eso nosotros imprimimos todos los elementos del mapa, primero la clave (key) y después el valor asociado (value).
El uso de mapas es muy importante y hay que aprender su uso de la mejor manera posible.

Comentarios en: "Procesamiento de la entrada" (1)

  1. muy bien, gracias , yo soy de las q m cuesta procesar la entrada jajajaja

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: