Problema ACM-ICPC. Automated Checking Machine


El pasado 8 de noviembre se efectuó el regional latinoamericano de programación competitiva, con vistas a determinar los equipos que clasificarán para la próxima competencia de la final mundial ACM-ICPC.

Esta competencia es uno de los eventos de programación que abarca a más universidades de diferentes países en el mundo, y los equipos que participan, son las mejores representaciones de programadores de cada institución, con la preparación necesaria para dar solución a diversos problemas en disimiles campos del conocimiento.

Dentro de los temas más generales que se ven en una competencia de programación, podemos encontrar:

  • Matemática
  • Teoría de grafos
  • Geometría computacional
  • Dinámica
  • Teoría de juegos

Esto son algunos de los temas que se tratan, claro que existen muchos más, pero tomaría un artículo entero mencionarlos todos. Con relación a este tema, comenzaremos dando solución a los problemas de este regional.

El primer problema que te mostraré, es el problema A de la competencia, titulado “Automated Checking Machine” (Máquina de chequeo automático). El autor de este problema es Ricardo Anido, de la universidad de Estadual de Campinas.

Descripción del problema:

La compañía de parte de computadoras para internet, es una tienda on-line que vende partes de computadoras. Pares de conectores eléctricos in-line, son las partes de computadoras más vendidas de la tienda. Sin embargo, también es una parte muy retornada a la tienda por los clientes no satisfechos, dado que encuentran errores al intentar conectar estos conectores nuevos a los que tenían los clientes en casa, por no ser compatibles.

Un conector in-line está compuesto por 5 puntos de conexión, etiquetados de 1 a 5. Cada punto de conexión de un conector puede ser un plug o un enchufe. Decimos que dos conectores son compatibles, si para cada etiqueta, en uno de los conectores es un plug y en el otro es un enchufe (en otras palabras, dos conectores son compatibles, si para cada punto de conexión con la misma etiqueta, un plug y un enchufe se encuentran conectados).

La Fig1 muestra un ejemplo de dos conectores que son compatibles y dos que no lo son.

Ejemplo de plugins compatibles y no compatibles

La compañía está introduciendo una Máquina de Chequeo automático, con un sensor óptico, que verifica cuándo dos conectores tomados por el cliente son compatibles. El complejo y costoso hardware está listo, pero se necesita tu ayuda para finalizar el software.

Dadas las descripciones de un par de conectores in-line, tu tarea es determinar si estos conectores son compatibles.

Entrada:

La primera línea tendrá 5 enteros Xi (0<=Xi<=1 para i=1,2,...,5), que representan los puntos de conexión del primer conector. La segunda línea tendrá 5 enteros Yi (0<=Yi<=1 para i=1,2,...,5), que representan los puntos de conexión, del segundo conector. En la entrada un 0 significa un enchufe y 1 un plug.

Salida:

Mostrar una línea con un caracter que represente cuando los conectores son compatibles o no. Si son compatibles mostrar la letra mayúscula Y; sino mostrar la letra mayúscula N.

Solución:

Primero tienes que entender lo que pide el problema, y para esto solo debes leer varias veces la descripción. Una vez que sabes lo que hay que hacer, tienes que leer las especificaciones de entrada y de salida, para que conozcas la forma en que se entrarán los datos y cómo se mostrará la solución al procesarse.

Una vez que hallas seguido estos pasos al pie de la letra, ya estás listo para dar solución al problema. Este ejercicio en particular fue el más fácil de la competencia, y para su solución, no era necesario tener un conocimiento avanzado en algoritmos de programación, dado que es de los problemas que catalogamos como Ad-hoc, esto significa que no tienen un mecanismo definido de solución.

La primera acción a realizar es leer las entradas del caso, que serán 10 números enteros repartidos a 5 por cada línea, donde los 5 primeros representan los puntos de conexión del primer conector y los otros 5, los del segundo conector.

Una vez leídos estos datos hay que verificar que los puntos de conexión semejantes de cada conector sean diferentes, en caso de que encontremos alguno que no cumpla esta condición, implica que no son compatibles, de otra forma, sí lo son.

La solución de este problema se las mostraré en el lenguaje de programación c++:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int conector1[5],conector2[5];
    //leemos el primer conector
    for(int i=0;i<5;i++){
        cin>>conector1[i];
    }
    //leemos el segundo conector
    for(int i=0;i<5;i++){
        cin>>conector2[i];
    }
    //inicialmente definimos que los conectores son compatibles
    bool compatibles=1;
    for(int i=0;i<5;i++){
        // comparamos el punto i de cada conector,
        // si son iguales, entonces los conectores no so compatibles
        if(conector1[i]==conector2[i]){
            compatibles=0;
            break;
        }
    }
    //mostramos la solución
    if(compatibles){
        cout<<"Y"<<endl;
    }else{
        cout<<"N"<<endl;
    }
    return 0;
}

Concluciones:

En próximas entradas daré solución a los demás problemas de esta competencia y explicaré las formas de solución de cada uno de ellos. Es un placer como siempre, y no olvides dejar tus dudas y sugerencias en los comentarios. Hasta la próxima.