Introducción
Cada año, la Asociación para la Maquinaria Computacional (ACM), organiza un concurso de programación a nivel mundial. Este concurso tiene dos fases: los concursos regionales y la Final Mundial. Este concurso de programación se celebra con un objetivo muy claro: sirve de escaparate de los mejores programadores del mundo para los representantes de grandes compañías en busca de talento. Cuando practiquéis para las competiciones de programación, recordad que todos vuestros esfuerzos deberían estar enfocados en mejorar tus habilidades de programación. No importa cual sea vuestra actuación en los concursos, no os decepcionéis. El éxito en los concursos de programación también se ve afectado por otros factores. Los más importantes son el factor adrenalina, el factor suerte, y el conjunto de problemas del concurso. Una forma de obtener observaciones sobre tus esfuerzos es participar en el Concurso / Práctica Online de la Universidad de Valladolid o en el Juez Virtual de la Universidad Estatal de los Urales. La resolución Online de problemas incrementa tu posición Online en las respectivas competiciones.
Este artículo es para principiantes. Trataré de los problemas comunes a los que todo el mundo se enfrenta durante los concursos y en la resolución de problemas en el Juez Online de la Universidad de Valladolid.(http://acm.uva.es/problemset) y en el Juez Online de la Universidad Estatal de los Urales (http://acm.timus.ru). Las sugerencias se dividen en tres partes: Sugerencias Generales, Sugerencias de Concursos Online, y Sugerencias Específicas de Valladolid. También hablaré brevemente acerca de los concursos de programación. A lo largo de todo el documento, se ha de tener en cuenta que en los concursos reales los jueces son humanos, y en los concursos Online, los jueces son programas de ordenador, a no ser que se especifique de otra forma.
Los diferentes tipos de Concursos de Programación
Muchos concursos de programación tienen lugar durante todo el año, como los Concursos Regionales de ACM, IOI, CEOI, y el Concurso POTM. El concurso de programación en vivo más prestigioso es el ACM ICPC (Concurso de Programación de Colegiados Internacionales de la Asociación de Maquinaria Computacional), y el concurso Online de programación más prestigioso es el IPSC (Concurso de Resolución de Problemas en Internet). En esta sección, trataré de algunos de estos concursos.
Concurso de Programación de Colegiados Internacionales de la Asociación de Maquinaria Computacional (ICPC-por sus iniciales en inglés)
Este concurso se celebra una vez al año. El primer ICPC tuvo lugar en 1977
. El concurso dura cinco horas. Generalmente, se plantean ocho problemas en inglés. Sin embargo, en las Finales Mundiales del 2001, se presentaron nueve problemas a los concursantes. Los concursos regionales se organizan de una forma similar. Cada equipo tiene tres personas, pero se da un solo ordenador por equipo. Los equipos entregan sus soluciones por medio de un software juez llamado PC^2 (PC al cuadrado) desarrollado en la CSUS (Universidad de Sacramento del Estado de California). Los lenguajes de programación permitidos son C/C++, Pascal y Java.
• Concursos Online
Es mucho más sencillo participar en los concursos Online que en los reales, puesto que no hay viajes o tensiones asociadas a ello
. Las reglas de entrega para los concursos Online de Valladolid y del Juez Online del USU son las mismas. Los concursantes tienen que enviar sus soluciones por correo electrónico a una determinada dirección e-mail. Las reglas del IPSC son bastante diferentes. El Organizador del Concurso IPSC proporciona entradas para los problemas. En lugar de enviar por correo electrónico sus soluciones, los concursantes tienen que enviar las salidas. Para obtener más información, visita las correspondientes páginas web.
Una diferencia muy importante entre los concursos en vivo y los concursos Online es que en los concursos en vivo tienes que trabajar en el mismo medio (sistema operativo, compiladores, configuración de los ordenadores) que los jueces, pero esto no tiene por que ser cierto en los concursos Online.
Algunos consejos para Concursantes
• Características de un buen equipo de programación
1. Debe tener conocimiento de los algoritmos estándar y la habilidad de encontrar el algoritmo apropiado para cada problema del conjunto.
2. La habilidad para implementar el algoritmo en un programa que funcione.
3. Estrategia de cooperación entre los miembros del equipo.
• Tipos Frecuentes de Problemas en los Conjuntos
- Problemas de Búsqueda
- Problemas de Grafos
- Problemas de Geometría
- Problemas de programación dinámica
- Problemas Triviales
- Problemas No Estándares
Los problemas de búsqueda incluyen problemas relacionados con búsqueda primero en anchura, y primero en profundidad. Los problemas de grafos incluyen problemas relacionados con teoría de grafos, como el camino más corto, número máximo de nodos, árbol de mínimo recorrido, etc... Los problemas de geometría incluyen problemas basados en geometría general y geometría computacional. La programación dinámica incluye problemas que tienen que ser resueltos con métodos tabulares. Los problemas triviales incluyen problemas sencillos, problemas que pueden ser resueltos sin mucho conocimiento de algoritmos, como problemas relacionados con números primos. Los problemas no estándares incluyen aquellos que no caen en ninguna de estas clases, como {cocción simulada}, el problema de las n-reinas, o incluso problemas basados en escritos de investigación. Por falta de espacio, no trataré estos tipos de problemas en detalle. Para aprender más acerca de cómo se eligen los problemas para un concurso, puedes leer el escrito de Tom Verhoeff
.
Lo que deberíais hacer para convertiros en un buen equipo
Los siguientes puntos pueden ser de ayuda para formar un buen equipo de concurso. Algunos de estos puntos están tomados de
.
1. Organizad tantos concursos de entrenamiento tan cercanos a los reales como sea posible.
2. Analizad primero el conjunto de problemas.
3. Intentad clasificar los problemas por grados de dificultad: fácil, moderado, complicado, etc...
4. Intentad resolver primero los problemas fáciles
5. Procurad no equivocaros al asignar una dificultad a un problema.
6. No es necesario que todos los miembros sean expertos en todas las áreas de programación, sino que todos deben ser eficientes en lo básico, como escritura de procedimientos, depuración y compilación.
7. Algunos pueden estar especializados en los problemas de búsqueda y de grafos, otros en programación dinámica, y al menos uno tiene que tener un profundo conocimiento de matemáticas.
8. Todos los miembros del equipo deberían conocer los puntos débiles y los fuertes de sus compañeros de equipo para que cuando se lea un problema, se sepa que miembro debería resolverlo.
9. No malgastes demasiado tiempo con un único problema. Puede que tus compañeros de equipo encuentren una solución adecuada más rápidamente.
10. Intentad leer todos los problemas.
11. Los miembros del equipo deberían tener buena comunicación entre ellos porque tendrán que decidir quien debería abandonar el ordenador y dejar que otro miembro se siente.
12. Pensad siempre en el bien del equipo. El concurso no es el momento más apropiado para ser egoísta. No pienses "¡Oh! He acabado mi cuota" o "Tengo que resolver un problema como sea o no me cogerán la próxima vez".
13. La forma más eficiente de escribir un programa es escribirlo en solitario, evitando la comunicación general y la confusión generada por distintos estilos de programación.
14. La resolución de problemas en conjunto también puede ser de ayuda. Esta estrategia funciona bien cuando el conjunto de problemas es complicado. También es buena para los equipos cuya meta es resolver como mucho un problema.
15. En un concurso de cinco horas, tenéis 15 horas manuales y cinco de ordenador. Por tanto, las horas de ordenador son extremadamente valiosas. Intentad no dejar desocupado el puesto del ordenador.
16. Si veis rechazado el problema más sencillo del concurso por errores tontos, suele ser una buena idea hacer que otro miembro del equipo rehaga el problema desde el principio.
17. Intentad ver las clasificaciones actuales, y averiguar también que problema es el que más se soluciona. Si vuestro equipo aún no ha resuelto ese problema, entonces intentad resolverlo inmediatamente.
18. Usad la silla delante del ordenador únicamente para teclear y no para pensar. Escribid vuestro programa en un papel, analizarlo, y usad entonces el ordenador.
19. Cuando los jueces rechacen vuestra solución, intentad pensar en vuestros errores más que sentarse delante del ordenador. La depuración en tiempo real es el error definitivo.
20. El sistema de puntuación de un concurso es digital, así que no podéis conseguir puntos por un problema resuelto al 99%. No intentéis atacar demasiados problemas al mismo tiempo. Al final del concurso, podéis encontraros con que habéis resuelto todos los problemas al 90% y que vuestro equipo está en la cola de la clasificación. Recordad siempre que los concursos de programación no son nada más {que problemas Knapsack 0/1, sólo que aquí puedes cogerlo todo}. Así que tendréis que resolverlo con una aproximación voraz - resolved los problemas más sencillos primero.
Los Diferentes Tipos de Respuestas de los Jueces
Las siguientes son los diferentes tipos de respuestas que os podéis encontrar en un concurso
:
• Correcto
Vuestro programa debe leer la entrada desde un fichero o desde la entrada estándar de acuerdo con la especificación del planteamiento del concurso. Los jueces comprobarán vuestro programa con sus entradas secretas. Si la salida de vuestro programa coincide con la salida de los jueces, se os dará esta respuesta.
• Salida Incorrecta
Si la salida de vuestro programa no coincide con lo que vuestros jueces esperan, os darán notificación de salida incorrecta. Las causas de salida incorrecta son:
1. Habéis entendido mal el problema
2. Se os ha pasado por alto algún detalle en el planteamiento. Los detalles son información que perderéis si no leéis el enunciado del problema cuidadosamente.
3. No habéis comprobado las condiciones extremas.
4. No tenéis experiencia suficiente para resolver el problema.
• Sin Salida
Vuestro programa no produce salida. Algunas causas posibles son:
1. Estáis malinterpretando el formato de entrada.
2. Vuestra selección del tipo de las variables es errónea.
3. Vuestro programa lee la entrada desde un archivo erroéno, por ejemplo, el juez está dando la entrada desde "a.in" pero vuestro programa lo lee desde "b.in".
4. Ha ocurrido un error de ejecución, pero el juez no ha podido detectarlo.
5. La ruta de acceso especificada en vuestro programa para el archivo de entrada es incorrecta. El archivo de entrada está, en la mayor parte de los casos, en el directorio actual.
• Error de Presentación
Este error ocurre cuando vuestro programa produce una salida correcta para la información secreta de los jueces, pero no la produce en el formato correcto. El error de presentación se tratará más adelante en este informe.
• Error de Ejecución
Esto error indica que vuestro programa realiza una operación ilegal cuando se ejecuta con la entrada del juez. Algunas operaciones ilegales son:
1. Referencia inválida a memoria. (El acceso fuera de los límites de un vector, un puntero que intenta acceder a una posición de memoria no asignada, o asignada por otros programas.)
2. División por cero. (El denominador de cualquier expresión es cero.)
3. Desbordamiento. (El valor de un tipo de datos excede su límite.)
4. Error de Dominio. (El dominio es incorrecto, como llamar a la función raíz cuadrada de un valor negativo.)
• Límite de Tiempo Excedido
En un concurso, el juez tiene especificado un tiempo límite para cada problema. Cuando tu programa no termina en el tiempo especificado, te dan este error. Algunas posibles causas son:
1. El uso de un algoritmo ineficiente (por ejemplo, intentar encontrar el factorial de un gran número de forma recursiva).
2. Bucle infinito.
3. La espera por la entrada desde el dispositivo de entrada estándar cuando el juez espera que lo toméis desde ficheros.
4. El asumir un formato incorrecto de los datos de entrada, por ejemplo, asumís que la entrada terminará con el carácter "#", cuando en realidad la entrada del juez termina con un final-de-fichero.
Sugerencias Generales para los Concursos
• Memoria Máxima
La memoria máxima permitida en la página de Valladolid es de 32 MB. Esta cantidad incluye la memoria para las variables globales, el heap, y la pila. Incluso si pensáis que habéis asignado mucho menos de 64 K de memoria, os daréis cuenta de que el juez normalmente os demostrará que ha sido asignada más memoria. También, no deberíais asignar más de 32 MB de memoria global, porque 32 MB es el máximo para todos los tipos de memoria. La memoria máxima para los concursos reales varía; para las Finales Mundiales es más de 128 MB.
• Los Problemas con los compiladores DOS y la asignación de memoria
A muchos de nosotros nos gusta usar compiladores DOS como el TURBO C++ 3.0 y el BORLAND C++ en el concurso, que no soportan la asignación de más de 64 K cada vez. {De forma que siempre es buena idea asignar memoria con una constante de forma que vuestras ejecuciones de prueba usen menos de 64 K de memoria, y antes de enviarlo, el tamaño de la memoria se pueda incrementar cambiando solamente el valor de la constante.} Si no practicáis esto, es muy probable que os encontréis con problemas como "Error de Ejecución", "Límite de Tiempo Excedido" y "Respuesta Incorrecta". Un ejemplo:
int const SIZE=100;
int store[SIZE][SIZE];
void initialize(void)
{
int i,j;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
store[j]=0;
}
• El error "Límite de Tiempo Excedido" no siempre es "Límite de Tiempo Excedido"
Cuando entreguéis un programa al juez, el juez os da una respuesta, pero esta respuesta no siempre es precisa. Por ejemplo, si asignáis menos memoria de la que es requerida, entonces puede que el programa no termine (puede que ni siquiera se aborte la ejecución), y el juez os dirá: "Límite de Tiempo Excedido". Una vez visto este mensaje, si tratáis de optimizar vuestro programa en lugar de corregir el problema de asignación de memoria vuestro programa nunca será aceptado. El ejemplo siguiente ilustra este problema. El esqueleto de vuestro programa es como sigue:
#include <stdio.h>
int const MAX=100;
int array[MAX],I;
void main(void)
{
for(i=0; i<=100;i++)
{
if(array==100)
{
array= -10000;
- - - - - -
- - - - - -
- - - - - -
}
}
}
En este ejemplo, se ha asignado una matriz de 100 elementos. Vuestro programa intentará acceder al elemento 100 de la matriz, que está fuera del alcance [0..99], a causa de un error en la sentencia del bucle for; en su lugar, accederá a la dirección de la variable contador i. Debido a que el valor de array[100] se pone a -10000, la variable contador se pondrá a -10000, de forma que la ejecución del bucle tomará mucho más tiempo y es posible que no termine en absoluto. De forma que el juez os da el mensaje "Límite de Tiempo Excedido", pero en realidad es un error de asignación de memoria.
• Probad el programa con varios conjuntos de datos
Siempre hay una entrada y una salida de ejemplo proporcionada con cada cuestión del concurso. Los concursantes sin experiencia que se vean incapaces de resolver ningún problema se ilusionan cuando la salida de uno de sus programas coincide con la salida ejemplo para la correspondiente entrada, y piensan que han resuelto el problema. Así que, sin malgastar ni un segundo, entregan el problema para que sea corregido y en muchos casos consiguen una respuesta de "erróneo". Un conjunto de datos no comprueba si las variables de tu programa se han inicializado correctamente, porque por defecto todas las variables globales tienen el valor cero (enteros = 0, caracteres = "\x0", reales = 0.0, y punteros = NULL). Incluso si los asignáis al principio del programa. {Incluso si usáis varios conjuntos de datos, el error puede seguir oculto si los conjuntos de datos son del mismo tamaño, a veces de tamaño decreciente o creciente}. Por tanto, el tamaño de la secuencia del conjunto de datos debería ser aleatorio. Es siempre una buena idea escribir una función separada para la inicialización.
• ¿Cómo tomar la entrada de reales en matrices?
Considerad el siguiente segmento de código:
#include <stdio.h>
float store[100];
void main(void)
{
int j;
for(j=0;j<100;j++)
scanf("%f",&store[j]);
}
Cuando este programa se ejecute, muchos compiladores de C/C++ mostrarán el error "Formato de Coma flotante no Enlazado". Para eliminar este error, tan sólo hace falta tomar la entrada en una variable normal de coma flotante, y entonces asignar dicha variable a la matriz, tal como sigue:
#include <stdio.h>
float store[100];
void main(void)
{
int j;
float temp;
for(j=0;j<100;j++)
{
scanf("%f",&temp);
store[j]=temp;
}
}
• Sugerencias de Mark Dettinger sobre los problemas de geometría
Mark Dettinger era el entrenador de la Universidad de ULM. Me sugirió que a veces es buena idea evitar los problemas de geometría a menos que uno tenga rutinas ya escritas. Las rutinas que pueden ser útiles son:
1. Intersección de dos rectas
2. Intersección de dos segmentos
3. Intersección de recta y segmento
4. Convexidad de una superficie/bóveda/curva {Casco convexo}
5. Punto interior a un polígono
6. Desde un gran número de puntos, cual es el número máximo de puntos en una sóla recta
7. El problema del par más cercano (Dado un conjunto de puntos, tenéis que encontrar el par de puntos más cercano entre ellos)
8. Tratad de aprender cómo se usa la función qsort() de C para ordenar enteros y registros.
9. El área de un polígono (Convexo o Cóncavo)
10. Centro de gravedad de un polígono (Convexo o Cóncavo)
11. Circunferencia Mínima (Para un número dado de puntos junto con sus coordenadas, encontrar la circunferencia con radio mínimo que les incluya a todos)
12. Esfera Mínima
13. Si un rectángulo entra {es interior a} en otro rectángulo (incluso rotándolo)
14. Intersección de dos circunferencias. Si no se produce la intersección, detectar la situación (si uno está dentro del otro, o si están lejos)
15. Algoritmos de recorte de rectas (contra un rectángulo, círculo, elipse).
• ¡Corregiré al juez!
Los jueces a veces omiten información que deberían haber dado. Por ejemplo, los jueces de mi país dan el error "Límite de Tiempo Excedido" pero nunca dicen cual es el límite de tiempo. En Valladolid, normalmente no se especifica el tamaño de la entrada (por ejemplo, el problema 497 - Iniciativa de defensa Estratégica). De forma que tratad de {sonsacar} a los jueces.
Suponed que no os dan el número máximo de entradas. Normalmente esto es una información vital por que si el número es pequeño, podéis usar backtracking, y si es grande, tenéis que usar técnicas como programación dinámica o backtracking con memorización. En el problema 497, no se da el posible número máximo de misiles a interceptar. Suponed que el bucle for (j=0;j<;100000000;j++) necesita 1 segundo de ejecución para el juez, y que N es el número de entradas dadas por el juez virtual, pero que no sabéis su valor. Entonces, enviad el siguiente programa con vuestro código. Ponedlo justo antes de que hayáis sabido el valor de N:
for(I=1;I<=20;I++)
{
if(I*1000>=N)
{
for(j=0;j<I*100000000;j++);
}
}
Ahora, de la ejecución de este programa podéis deducir el número de la entrada N. Usando este método también podéis determinar cuanto más rápido es el ordenador del juez que el vuestro, y así averiguar el límite aproximado de tiempo para cualquier problema en vuestro ordenador. La mayoría de los concursos en vivo tienen una sesión de práctica antes del concurso. Ese día, debéis tratar de determinar la velocidad del ordenador del juez enviando muchos programas que consistan de muchos bucles y bucles anidados.
(
La Historia del Problema de la Final Mundial del 2000:
¿Sabiaís que hubo un error en el problema de la Final Mundial del 2000?. El problema culpable era el problema F. La especificación del problema decía que el grafo de entrada debía ser completo, pero no todas las entradas del juez eran grafos completos. Uno de los equipos <;puede que otros también> enviaron un programa que comprobaba si el grafo de entrada era completo. Si el grafo de entrada era incompleto, entonces su programa entraba en un bucle infinito. De forma que la respuesta del juez era "Límite de Tiempo Excedido". De esta respuesta ellos fueron capaces de deducir que alguno de los grafos de entrada era incompleto, y resolvieron el problema de acuerdo con esto.)
• Usad doble precisión en lugar de reales simples (double en lugar de float)
Es siempre buena idea usar un 'double' en lugar de un 'float', puesto que el 'double' da más precisión y rango. Recordad siempre que existe un tipo de datos llamado 'long double'. En el C/C++ de Unix/Linux, hay también un 'long long integer', y el Juez Virtual corre bajo Linux. Algunas veces se especifica en el enunciado del problema el uso del tipo 'float'. En esos casos, usad 'floats'.
• Uso avanzado de printf() y scanf()
Aquellos que hayáis olvidado el uso avanzado de printf() y scanf(), recordad los siguientes ejemplos:
scanf("%[ABCDEFGHIJKLMNOPQRSTUVWXYZ]",&linea);
//donde linea es una cadena
Esta llamada a la función scanf() toma sólo las letras mayúsculas como entrada para la línea, y cualquier otro carácter que no sea A..Z finaliza la cadena. De forma similar, la siguiente llamada a la función scanf() se comportará igual que un gets():
scanf("%[^\n]",linea); // donde linea es una cadena
Aprended los caracteres finalizadores por defecto de la función scanf(). Intentad leer todas las características avanzadas de scanf() y de printf(). Esto os ayudará a la larga.
• Uso de nueva línea con scanf()
Si el contenido de un archivo (input.txt) es:
abc
def
y el siguiente programa se ejecuta para que tome la entrada del archivo:
char input[100],ch;
void main(void)
{
freopen("input.txt","rb",stdin);
scanf("%s",&input);
scanf("%c",&ch);
}
¿Cuál será el valor de input y ch?
Aquí tenemos una modificación del código:
char input[100],ch;
void main(void)
{
freopen("input.txt","rb",stdin);
scanf("%s\n",&input);
scanf("%c",&ch);
}
¿Cuál será su valor ahora?
El valor de ch será '\n' para el primer segmento de código, y 'd' para el segundo.
• Memorizad el valor de pi
Siempre deberíais intentar recordad el valor de pi con tantos decimales como sea posible.
3.1415926535897932384626433832795, quizá la parte en negrita. Puede que los jueces no os den el valor en la pregunta, y si usáis valores como 22/7 o 3.1416 o 3.142857, es muy posible que alguna de las entradas críticas de los jueces os den la respuesta por incorrecta. También podéis obtener el valor de pi como una constante definida por el compilador, o del siguiente código:
pi=2*acos(0);
• Problemas con la igualdad de números en coma flotante (precisión doble o simple)
No siempre podéis comprobar la igualdad de números en coma flotante con el operador == en C/C++. Lógicamente, sus valores pueden ser los mismos, pero debido al límite en la precisión y a errores de redondeo pueden diferir en una pequeña cantidad, y pueden ser considerados desiguales incorrectamente por vuestro programa. Por tanto, para comprobar la igualdad de dos números a y b en coma flotante, podéis usar un fragmento de código como el que sigue:
if (fabs(a-b)<;ERROR) printf("Son iguales.\n";
Aquí, ERROR es un valor en coma flotante muy pequeño, algo así como 1e-15. En realidad, 1e-15 es el valor por defecto que los jueces escritores de soluciones usan. Este valor puede cambiarse si la precisión se especifica en el enunciado del problema.
• Los astutos jueces...
Los jueces siempre tratan de hacer largos los enunciados de problemas fáciles y los enunciados de los problemas difíciles más cortos para hacerlos parecer muy fáciles. Por ejemplo, un enunciado de un problema puede ser: "Encontrar el área común de dos polígonos". El enunciado es sencillo, pero la solución es muy difícil. Otro ejemplo es: "Para un número dado encontrar dos números iguales cuyo producto sea igual a ese número dado". Aunque el segundo enunciado es más largo que el primero, el enunciado del segundo problema sólo pregunta encontrar la raíz cuadrada de un número, que se puede hacer usando una función predefinida del compilador.
• Usad la función assert()
Casi siempre está bien usar la función de C/C++ assert(), que está en el fichero de cabecera assert.h. Con la función assert(), podéis comprobar el valor predefinido de una variable o de una expresión en una cierta etapa de vuestro programa. Si por alguna razón, la variable o expresión no tiene el valor especificado, assert() imprimirá un mensaje de error. Echadle un vistazo a la documentación C/C++ para más detalles.
• Evitar la recursividad
Siempre es buena idea evitar la recursividad en los concursos de programación, pues la recursividad lleva más tiempo, y los programas recursivos abortan la ejecución de manera mucho más frecuente (especialmente en el caso de un {análisis}), y para alguna gente es mucho más difícil de depurar. Pero la recursividad no debería estar descartada por sistema, pues muchos problemas son muy sencillos si se resuelven recursivamente (DFS, backtracking), y hay gente a la que le gusta pensar recursivamente. Sin embargo, es un mal hábito resolver problemas de forma recursiva que pueden ser resueltos fácilmente de forma no iterativa, como por ejemplo el factorial de un número, la generación de la serie de Fibonacci, y la búsqueda primero en anchura. En los concursos de programación en vivo, no vale la pena escribir código clásico. El código clásico es {tacaño}, normalmente difícil de comprender y de depurar, aunque muestre la brillantez del programador. Como por ejemplo, el código para intercambiar dos valores, que puede ser escrito de forma clásica como sigue:
#define swap(xxx,yyy) (xxx)^=(yyy)^=(xxx)^=(yyy)
Sin embargo, en un concurso no conseguiréis puntos extra por este tipo de implementación.
• Mejorad vuestra comprensión de la probabilidad y de los juegos de cartas
Tener una buena comprensión de la probabilidad es vital para ser un buen programador. Si queréis medir vuestra comprensión de la probabilidad, resolved el problema 556 de Valladolid y {sufrid} un libro de estadística sobre probabilidad. Aprendeos teoremas de probabilidad, sucesos dependientes e independientes, y probabilidad del cara / cruz. También deberíais ser capaces de resolver los problemas comunes relativos a juegos de cartas.
• Tened cuidado al usar gets() y scanf() a la vez
Deberíais tener cuidado al usar gets() y scanf() en el mismo programa. Probadlo con el siguiente caso. El código es:
scanf("%s\n",&dummy);
gets(nombre);
Y si el fichero de entrada es:
ABCDEF
bbbbbXXX
¿Qué tendríais como valor del nombre? "XXX" o "bbbbbbXXX" (Aquí la b significa un espacio).
Sugerencias para los Jueces Online basados en UNIX y para los concursos
• Portabilidad de Funciones
No todas las funciones C/C++ disponibles en DOS lo están en UNIX. Comprobad la documentación para ver la portabilidad entre distintos sistemas operativos. Si una función es portable a UNIX, podéis usarla para resolver problemas en la página de Valladolid y del USU. Usad sólo entrada estándar y funciones de salida para tomar entradas y producir salidas.
• itoa(), la función importante que UNIX NO tiene
UNIX no soporta la útil función itoa(). Un modo de sustituir esta función puede ser:
char numstr[100];
int num=1200;
sprintf(numstr,"%d",num); // a decimal
sprintf(numstr,"%X",num); //a hexadecimal en mayúsculas
Intentad sustituir cualquier otra función que no esté disponible en UNIX/LINUX.
• Problemas con la configuración del programa de correo
Algunos problemas no serán aceptados incluso cuando estén correctamente resueltos. Tales problemas son el 371 - la función de Ackermann, el 336 - un nodo demasiado lejano, el 466 - espejo, espejo, etc... Esto se debe a que nuestros programas de correo electrónico (por ejemplo, el Outlook Express, el Eudora, etc...) rompen las líneas más largas, y estos problemas tienen líneas largas en su salida. Así que en el Outlook Express deberíais ir a Herramientas -> Opciones -> Envío -> Configuración de Envío de Texto, y cambiar la opción de {Automatically Wrap Text} de 76 (por defecto) a 132. Se pueden encontrar opciones similares en otros programas de correo. El Juez Virtual de USU tiene un impreso de entrega de programa con el que podéis enviar directamente vuestro programa sin enviar un e-mail. Recordad que el problema con los parámetros del programa de correo puede causar tanto una respuesta errónea como un error de compilación.
• ¿Qué es el error de presentación?
Los errores de presentación son errores que no están causados por errores algorítmicos ni lógicos. Hay una diferencia entre el error de presentación de los jueces virtuales y el de los jueces en vivo. Los últimos son capaces de detectar los fallos, como faltas de ortografía, palabras extra, espacios extra, etc... y diferenciarlos de los errores algorítmicos, como {coste} erróneo, decisiones erróneas, etc... Estos errores son los errores de presentación tal como los clasifican los jueces humanos. Por otro lado, los jueces virtuales comparan la salida del juez y la del concursante con la ayuda de un programa de comparación de ficheros, de forma que incluso las faltas de ortografía pueden causar una "respuesta errónea". Generalmente, cuando el programa de comparación de ficheros encuentra líneas adicionales, éstas se consideran error de presentación. Los jueces humanos, por el contrario, no suelen detectar estos errores. Pero, hoy en día, los ordenadores se van volviendo más potentes, se usan entradas de juicio más grandes y se generan archivos de salida más grandes. Por tanto, en los concursos en vivo, se usan programas juez especiales que pueden detectar errores de presentación, múltiples soluciones correctas, etc... Avanzamos hacía mejores juicios {correcciones} y hacia una mejor habilidad de programación. Estadísticas recientes de ACM
demuestran que la participación en el Concurso de Programación para Colegiados de ACM se está incrementando drásticamente y que en un futuro cercano se intensificará la competición en el concurso de programación . Así que la mejora del sistema de juicio es casi una necesidad.
• Un error común de los concursantes
Recientemente, he organizado varios concursos (en colaboración con Rezaul Alam Chowdhury y en colaboración con la UVA) y he visto cómo los concursantes cometen muchos errores tontos. El error más destacable es dar las cosas por hechas. En un problema, especifiqué que las entradas serían enteros (tal como se definen en matemáticas) pero no especifiqué el rango de entrada y muchos concursantes asumieron que el rango sería 0..(2^32-1). Pero, en realidad se dieron muchos números grandes como entrada. El tamaño máximo del fichero de entrada se especificaba de lo que uno podría asumir que era el número máximo posible. Había también algunos números negativos en la entrada (los enteros pueden ser negativos).
• Las causas de un error de compilación
El error de compilación es un error común en la página de Valladolid. Puede parecer sorprendente el compilar y ejecutar un programa, enviárselo al Juez Virtual y obtener un error de compilación. Las causas más comunes para este error son:
1. La omisión de los ficheros #include:
Algunos de los compiladores que usamos no requieren incluir los ficheros de cabecera incluso cuando usamos funciones bajo estos ficheros de cabecera. Pero el Juez Virtual nunca lo permite. Por ejemplo, algunas funciones existen tanto en math.h y en stdlib.h. Para el Juez Virtual, necesitas incluir ambos ficheros de cabecera si quieres usar dichas funciones.
2. No especificar el lenguaje correcto:
Otra causa del "Errode Compilación" es no espeficiar el lenguaje correcto. Normalmente, cuando programamos en C, usamos las facilidades disponibles en C++, y entonces especificamos el lenguaje como si fuese C y obtenemos un error de compilación. Por ejemplo, el siguiente puede ser compilado como un programa de C en nuestro entorno Dos/Windows, pero no en UNIX/LINUX (los Jueces Virtuales).
for (int i=0;i<;100;i++)
{
printf("Error de Compilación\n";
}
3. El formato de envío de los e-mail
Los e-mail enviados al Juez Virtual deberían estar en formato de texto plano. Si el tipo de e-mail es texto enriquecido o HTML, el programa no se compilará. No deberíais enviar vuestro programa como un attachment.
4. Los caracteres misteriosos
Cuando empecé a programar para Valladolid al principio, usaba Turbo C++. Después de que acabé satisfactoriamente un programa, abrí el código fuente con el Bloc de Notas, seleccioné todo el texto, lo copié y lo pegué en mi editor de correo, y después lo envié a la página de Valladolid y obtuve un error de compilación. No pude descubrir la causa. Un día, lo pegué en mi editor de correo, lo grabé como un fichero de texto, después lo abrí en mi editor de texto del DOS, y descubrí algunos caracteres misteriosos en el fichero de texto, que eran invisibles en Windows. Ya no he vuelto a tener el mismo problema. Si algunos de vosotros obtenéis un error de compilación por razones desconocidas, por favor comprobad si ésta es la razón. Así, si obtenéis un mensaje de error de compilación y no podéis descubrir la causa, comprobad si vuestro programa de correo o editor de texto está añadiendo símbolos adicionales a vuestro código.
5. El uso de funciones no portables
Los errores de compilación están causados por el uso de funciones que sólo están disponibles en DOS y no en LINUX, como strrev(), itoa(), etc...
6. El uso de comentarios de estilo del C++
El C++ permite comentarios de estilo que comienzan con //. Si el programa de correo recorta el comentario a dos líneas, podéis encontraros con un error de compilación.
Algunas sugerencias específicas para Valladolid
Las siguientes son varias sugerencias para la resolución de problemas para el Juez Virtual de Valladolid:
• Tipos de entrada en el Juez Virtual de Valladolid
Existen cuatro tipos de entrada en el Juez Virtual (Último cambio)
1. Entrada no - múltiple sin programa especial de corrección (Bandera Roja)
2. Entrada no - múltiple con programa especial de corrección (Bandera Naranja)
3. Entrada múltiple sin programa especial de corrección (Bandera Azul)
4. Entrada múltiple con programa especial de corrección (Bandera Verde)
•¿Qué es un programa de corrección especial?
Existen algunos problemas que sólo tienen una única salida para una única entrada, pero otros problemas pueden tener más de una salida para la misma entrada. Por ejemplo, si os preguntan cual es la cadena de longitud 3 que más aparece en la cadena "abcabcabcijkijkijk", desafortunadamente la respuesta puede ser tanto "abc" como "ijk". Por tanto, si vuestro programa devuelve "abc", es correcto, si devuelve "ijk" es también correcto. El programa juez no puede determinar la corrección de vuestro programa simplemente comparando vuestra salida con la del programa del juez. El juez debe escribir un programa especial, que leerá vuestra respuesta y determinará si es correcta o no. Este programa especial se describe como un programa especial de corrección en el Juez Virtual de Valladolid. Para los problemas con programa especial de corrección (Problemas 104, 120, 135, etc... o los programas con bandera verde o naranja) ni podéis estar seguros de que vuestro programa sea incorrecto incluso si la salida de vuestro programa no coincide con la salida de ejemplo para una entrada dada de ejemplo.
Los "Programas de Entrada Múltiple" son un invento del Juez Virtual. He aquí la razón por la que han nacido los programas de entrada múltiple. El Juez Virtual utiliza normalmente los problemas y los datos que se usaron en los concursos en vivo. Hay algunos problemas en los concursos en vivo cuyas soluciones toman un solo conjunto de datos, da la salida correspondiente, y termina. Esto no implica que los jueces den sólo un conjunto de datos. En realidad los jueces dan varios ficheros como entrada, uno después de otro, y comparan los correspondientes ficheros de salida con la salida del juez. Sin embargo, la política del Juez Virtual de Valladolid es diferente. Siempre prefiere dar un único archivo como entrada. Inserta todas las entradas del juez en un único fichero y en el comienzo de ese fichero escribe cuantos conjuntos de datos habrá. Este número es el mismo que el número de ficheros de entrado que usan los jueces del concurso. Una línea en blanco separa cada conjunto de datos. Por tanto, la estructura del fichero de entrada para un programa de entrada múltiple es como sigue:
integer N //que denota el número de conjuntos de entrada
--- línea en blanco ---
conjunto de entradas 1 /* como esté descrito en el enunciado del problema */
--- línea en blanco ---
conjunto de entradas 2 /* como esté descrito en el enunciado del problema */
--- línea en blanco ---
conjunto de entradas 3 /* como esté descrito en el enunciado del problema */
.
.
.
--- línea en blanco ---
conjunto de entradas N /* como esté descrito en el enunciado del problema */
--- final del fichero ---
Fijaos en que no hay línea en blanco después del último conjunto de datos (a veces puede haberla, por tanto, comprobad ambas posibilidades). La estructura de un fichero de salida para una entrada múltiple será:
salida para el conjunto 1 /* como esté descrito en el enunciado del problema */
--- línea en blanco ---
salida para el conjunto 2 /* como esté descrito en el enunciado del problema */
--- línea en blanco ---
salida para el conjunto 3 /* como esté descrito en el enunciado del problema */
--- línea en blanco ---
.
.
.
--- línea en blanco ---
salida para el conjunto N /* como esté descrito en el enunciado del problema */
--- final de fichero ---
El Juez Virtual de la USU no tiene programas de entrada múltiple como el de Valladolid. Prefiere dar múltiples ficheros como entrada y asigna un tiempo límite para cada entrada.
• Problemas de los Programas de Entrada Múltiple
Existen algunos puntos que deberíais considerar para los programas de entrada múltiple.
1. Incluso si la especificación de entrada dice que la entrada termina con el final de fichero (EOF), cada conjunto de entradas finaliza en realidad con una línea en blanco, excepto para el último, que termina con el final de fichero.
2. Tened cuidado con la inicialización de las variables. Si no se inicializan de forma correcta, vuestro programa puede funcionar para un único conjunto de datos pero dar salida correcta {incorrecta} para varios conjuntos de datos. Todas las variables globales se inicializan a sus correspondientes ceros. Así, para un único conjunto de entradas, la inicialización puede no ser necesaria, pero para múltiples entradas, es un requisito.
• La sección de "Arreglando Errores"
Aseguraos siempre de echarle un vistazo a la sección de Arreglando Errores del Juez de Valladolid. Algunos de los problemas del Juez Virtual de Valladolid tienen errores. Algunos de los errores se han corregido en esta página.
• Leer el Tablón de Mensajes
Intentad siempre leer el tablón de mensajes del sitio de Valladolid. Aprenderéis muchas cosas de otros programadores. El Juez Virtual de la USU también tiene un tablón de mensajes. Podéis también enviar vuestros propios puntos de vista y problemas por medio de estos tablones.
Conclusión
Mucha gente tiene la idea general de que aquel que conoce más algoritmos es el mejor programador. Pero como en el proverbio {"There are many a slip in between the cup and the lip"}, esta idea no es cierta. Para ser un programador mejor, necesitas tener una muy buena comprensión de las matemáticas. La resolución de un montón de problemas de matemáticas te ayudará a mejorar tu capacidad analítica, que es el rasgo más importante de un buen programador. Me he dado cuenta de que resolver tipos diferentes de problemas de geometría ayuda especialmente en la mejora de la capacidad analítica de cualquiera. Como concursantes, no debéis nunca perder los nervios durante un concurso. No podéis ser mejores programadores de lo que realmente sois, pero en el concurso deberíais intentar hacerlo siempre lo mejor que podáis.
jajaja puro copy pero sirve
Cada año, la Asociación para la Maquinaria Computacional (ACM), organiza un concurso de programación a nivel mundial. Este concurso tiene dos fases: los concursos regionales y la Final Mundial. Este concurso de programación se celebra con un objetivo muy claro: sirve de escaparate de los mejores programadores del mundo para los representantes de grandes compañías en busca de talento. Cuando practiquéis para las competiciones de programación, recordad que todos vuestros esfuerzos deberían estar enfocados en mejorar tus habilidades de programación. No importa cual sea vuestra actuación en los concursos, no os decepcionéis. El éxito en los concursos de programación también se ve afectado por otros factores. Los más importantes son el factor adrenalina, el factor suerte, y el conjunto de problemas del concurso. Una forma de obtener observaciones sobre tus esfuerzos es participar en el Concurso / Práctica Online de la Universidad de Valladolid o en el Juez Virtual de la Universidad Estatal de los Urales. La resolución Online de problemas incrementa tu posición Online en las respectivas competiciones.
Este artículo es para principiantes. Trataré de los problemas comunes a los que todo el mundo se enfrenta durante los concursos y en la resolución de problemas en el Juez Online de la Universidad de Valladolid.(http://acm.uva.es/problemset) y en el Juez Online de la Universidad Estatal de los Urales (http://acm.timus.ru). Las sugerencias se dividen en tres partes: Sugerencias Generales, Sugerencias de Concursos Online, y Sugerencias Específicas de Valladolid. También hablaré brevemente acerca de los concursos de programación. A lo largo de todo el documento, se ha de tener en cuenta que en los concursos reales los jueces son humanos, y en los concursos Online, los jueces son programas de ordenador, a no ser que se especifique de otra forma.
Los diferentes tipos de Concursos de Programación
Muchos concursos de programación tienen lugar durante todo el año, como los Concursos Regionales de ACM, IOI, CEOI, y el Concurso POTM. El concurso de programación en vivo más prestigioso es el ACM ICPC (Concurso de Programación de Colegiados Internacionales de la Asociación de Maquinaria Computacional), y el concurso Online de programación más prestigioso es el IPSC (Concurso de Resolución de Problemas en Internet). En esta sección, trataré de algunos de estos concursos.
Concurso de Programación de Colegiados Internacionales de la Asociación de Maquinaria Computacional (ICPC-por sus iniciales en inglés)
Este concurso se celebra una vez al año. El primer ICPC tuvo lugar en 1977
. El concurso dura cinco horas. Generalmente, se plantean ocho problemas en inglés. Sin embargo, en las Finales Mundiales del 2001, se presentaron nueve problemas a los concursantes. Los concursos regionales se organizan de una forma similar. Cada equipo tiene tres personas, pero se da un solo ordenador por equipo. Los equipos entregan sus soluciones por medio de un software juez llamado PC^2 (PC al cuadrado) desarrollado en la CSUS (Universidad de Sacramento del Estado de California). Los lenguajes de programación permitidos son C/C++, Pascal y Java.
• Concursos Online
Es mucho más sencillo participar en los concursos Online que en los reales, puesto que no hay viajes o tensiones asociadas a ello
. Las reglas de entrega para los concursos Online de Valladolid y del Juez Online del USU son las mismas. Los concursantes tienen que enviar sus soluciones por correo electrónico a una determinada dirección e-mail. Las reglas del IPSC son bastante diferentes. El Organizador del Concurso IPSC proporciona entradas para los problemas. En lugar de enviar por correo electrónico sus soluciones, los concursantes tienen que enviar las salidas. Para obtener más información, visita las correspondientes páginas web.
Una diferencia muy importante entre los concursos en vivo y los concursos Online es que en los concursos en vivo tienes que trabajar en el mismo medio (sistema operativo, compiladores, configuración de los ordenadores) que los jueces, pero esto no tiene por que ser cierto en los concursos Online.
Algunos consejos para Concursantes
• Características de un buen equipo de programación
1. Debe tener conocimiento de los algoritmos estándar y la habilidad de encontrar el algoritmo apropiado para cada problema del conjunto.
2. La habilidad para implementar el algoritmo en un programa que funcione.
3. Estrategia de cooperación entre los miembros del equipo.
• Tipos Frecuentes de Problemas en los Conjuntos
- Problemas de Búsqueda
- Problemas de Grafos
- Problemas de Geometría
- Problemas de programación dinámica
- Problemas Triviales
- Problemas No Estándares
Los problemas de búsqueda incluyen problemas relacionados con búsqueda primero en anchura, y primero en profundidad. Los problemas de grafos incluyen problemas relacionados con teoría de grafos, como el camino más corto, número máximo de nodos, árbol de mínimo recorrido, etc... Los problemas de geometría incluyen problemas basados en geometría general y geometría computacional. La programación dinámica incluye problemas que tienen que ser resueltos con métodos tabulares. Los problemas triviales incluyen problemas sencillos, problemas que pueden ser resueltos sin mucho conocimiento de algoritmos, como problemas relacionados con números primos. Los problemas no estándares incluyen aquellos que no caen en ninguna de estas clases, como {cocción simulada}, el problema de las n-reinas, o incluso problemas basados en escritos de investigación. Por falta de espacio, no trataré estos tipos de problemas en detalle. Para aprender más acerca de cómo se eligen los problemas para un concurso, puedes leer el escrito de Tom Verhoeff
.
Lo que deberíais hacer para convertiros en un buen equipo
Los siguientes puntos pueden ser de ayuda para formar un buen equipo de concurso. Algunos de estos puntos están tomados de
.
1. Organizad tantos concursos de entrenamiento tan cercanos a los reales como sea posible.
2. Analizad primero el conjunto de problemas.
3. Intentad clasificar los problemas por grados de dificultad: fácil, moderado, complicado, etc...
4. Intentad resolver primero los problemas fáciles
5. Procurad no equivocaros al asignar una dificultad a un problema.
6. No es necesario que todos los miembros sean expertos en todas las áreas de programación, sino que todos deben ser eficientes en lo básico, como escritura de procedimientos, depuración y compilación.
7. Algunos pueden estar especializados en los problemas de búsqueda y de grafos, otros en programación dinámica, y al menos uno tiene que tener un profundo conocimiento de matemáticas.
8. Todos los miembros del equipo deberían conocer los puntos débiles y los fuertes de sus compañeros de equipo para que cuando se lea un problema, se sepa que miembro debería resolverlo.
9. No malgastes demasiado tiempo con un único problema. Puede que tus compañeros de equipo encuentren una solución adecuada más rápidamente.
10. Intentad leer todos los problemas.
11. Los miembros del equipo deberían tener buena comunicación entre ellos porque tendrán que decidir quien debería abandonar el ordenador y dejar que otro miembro se siente.
12. Pensad siempre en el bien del equipo. El concurso no es el momento más apropiado para ser egoísta. No pienses "¡Oh! He acabado mi cuota" o "Tengo que resolver un problema como sea o no me cogerán la próxima vez".
13. La forma más eficiente de escribir un programa es escribirlo en solitario, evitando la comunicación general y la confusión generada por distintos estilos de programación.
14. La resolución de problemas en conjunto también puede ser de ayuda. Esta estrategia funciona bien cuando el conjunto de problemas es complicado. También es buena para los equipos cuya meta es resolver como mucho un problema.
15. En un concurso de cinco horas, tenéis 15 horas manuales y cinco de ordenador. Por tanto, las horas de ordenador son extremadamente valiosas. Intentad no dejar desocupado el puesto del ordenador.
16. Si veis rechazado el problema más sencillo del concurso por errores tontos, suele ser una buena idea hacer que otro miembro del equipo rehaga el problema desde el principio.
17. Intentad ver las clasificaciones actuales, y averiguar también que problema es el que más se soluciona. Si vuestro equipo aún no ha resuelto ese problema, entonces intentad resolverlo inmediatamente.
18. Usad la silla delante del ordenador únicamente para teclear y no para pensar. Escribid vuestro programa en un papel, analizarlo, y usad entonces el ordenador.
19. Cuando los jueces rechacen vuestra solución, intentad pensar en vuestros errores más que sentarse delante del ordenador. La depuración en tiempo real es el error definitivo.
20. El sistema de puntuación de un concurso es digital, así que no podéis conseguir puntos por un problema resuelto al 99%. No intentéis atacar demasiados problemas al mismo tiempo. Al final del concurso, podéis encontraros con que habéis resuelto todos los problemas al 90% y que vuestro equipo está en la cola de la clasificación. Recordad siempre que los concursos de programación no son nada más {que problemas Knapsack 0/1, sólo que aquí puedes cogerlo todo}. Así que tendréis que resolverlo con una aproximación voraz - resolved los problemas más sencillos primero.
Los Diferentes Tipos de Respuestas de los Jueces
Las siguientes son los diferentes tipos de respuestas que os podéis encontrar en un concurso
:
• Correcto
Vuestro programa debe leer la entrada desde un fichero o desde la entrada estándar de acuerdo con la especificación del planteamiento del concurso. Los jueces comprobarán vuestro programa con sus entradas secretas. Si la salida de vuestro programa coincide con la salida de los jueces, se os dará esta respuesta.
• Salida Incorrecta
Si la salida de vuestro programa no coincide con lo que vuestros jueces esperan, os darán notificación de salida incorrecta. Las causas de salida incorrecta son:
1. Habéis entendido mal el problema
2. Se os ha pasado por alto algún detalle en el planteamiento. Los detalles son información que perderéis si no leéis el enunciado del problema cuidadosamente.
3. No habéis comprobado las condiciones extremas.
4. No tenéis experiencia suficiente para resolver el problema.
• Sin Salida
Vuestro programa no produce salida. Algunas causas posibles son:
1. Estáis malinterpretando el formato de entrada.
2. Vuestra selección del tipo de las variables es errónea.
3. Vuestro programa lee la entrada desde un archivo erroéno, por ejemplo, el juez está dando la entrada desde "a.in" pero vuestro programa lo lee desde "b.in".
4. Ha ocurrido un error de ejecución, pero el juez no ha podido detectarlo.
5. La ruta de acceso especificada en vuestro programa para el archivo de entrada es incorrecta. El archivo de entrada está, en la mayor parte de los casos, en el directorio actual.
• Error de Presentación
Este error ocurre cuando vuestro programa produce una salida correcta para la información secreta de los jueces, pero no la produce en el formato correcto. El error de presentación se tratará más adelante en este informe.
• Error de Ejecución
Esto error indica que vuestro programa realiza una operación ilegal cuando se ejecuta con la entrada del juez. Algunas operaciones ilegales son:
1. Referencia inválida a memoria. (El acceso fuera de los límites de un vector, un puntero que intenta acceder a una posición de memoria no asignada, o asignada por otros programas.)
2. División por cero. (El denominador de cualquier expresión es cero.)
3. Desbordamiento. (El valor de un tipo de datos excede su límite.)
4. Error de Dominio. (El dominio es incorrecto, como llamar a la función raíz cuadrada de un valor negativo.)
• Límite de Tiempo Excedido
En un concurso, el juez tiene especificado un tiempo límite para cada problema. Cuando tu programa no termina en el tiempo especificado, te dan este error. Algunas posibles causas son:
1. El uso de un algoritmo ineficiente (por ejemplo, intentar encontrar el factorial de un gran número de forma recursiva).
2. Bucle infinito.
3. La espera por la entrada desde el dispositivo de entrada estándar cuando el juez espera que lo toméis desde ficheros.
4. El asumir un formato incorrecto de los datos de entrada, por ejemplo, asumís que la entrada terminará con el carácter "#", cuando en realidad la entrada del juez termina con un final-de-fichero.
Sugerencias Generales para los Concursos
• Memoria Máxima
La memoria máxima permitida en la página de Valladolid es de 32 MB. Esta cantidad incluye la memoria para las variables globales, el heap, y la pila. Incluso si pensáis que habéis asignado mucho menos de 64 K de memoria, os daréis cuenta de que el juez normalmente os demostrará que ha sido asignada más memoria. También, no deberíais asignar más de 32 MB de memoria global, porque 32 MB es el máximo para todos los tipos de memoria. La memoria máxima para los concursos reales varía; para las Finales Mundiales es más de 128 MB.
• Los Problemas con los compiladores DOS y la asignación de memoria
A muchos de nosotros nos gusta usar compiladores DOS como el TURBO C++ 3.0 y el BORLAND C++ en el concurso, que no soportan la asignación de más de 64 K cada vez. {De forma que siempre es buena idea asignar memoria con una constante de forma que vuestras ejecuciones de prueba usen menos de 64 K de memoria, y antes de enviarlo, el tamaño de la memoria se pueda incrementar cambiando solamente el valor de la constante.} Si no practicáis esto, es muy probable que os encontréis con problemas como "Error de Ejecución", "Límite de Tiempo Excedido" y "Respuesta Incorrecta". Un ejemplo:
int const SIZE=100;
int store[SIZE][SIZE];
void initialize(void)
{
int i,j;
for(i=0;i<SIZE;i++)
for(j=0;j<SIZE;j++)
store[j]=0;
}
• El error "Límite de Tiempo Excedido" no siempre es "Límite de Tiempo Excedido"
Cuando entreguéis un programa al juez, el juez os da una respuesta, pero esta respuesta no siempre es precisa. Por ejemplo, si asignáis menos memoria de la que es requerida, entonces puede que el programa no termine (puede que ni siquiera se aborte la ejecución), y el juez os dirá: "Límite de Tiempo Excedido". Una vez visto este mensaje, si tratáis de optimizar vuestro programa en lugar de corregir el problema de asignación de memoria vuestro programa nunca será aceptado. El ejemplo siguiente ilustra este problema. El esqueleto de vuestro programa es como sigue:
#include <stdio.h>
int const MAX=100;
int array[MAX],I;
void main(void)
{
for(i=0; i<=100;i++)
{
if(array==100)
{
array= -10000;
- - - - - -
- - - - - -
- - - - - -
}
}
}
En este ejemplo, se ha asignado una matriz de 100 elementos. Vuestro programa intentará acceder al elemento 100 de la matriz, que está fuera del alcance [0..99], a causa de un error en la sentencia del bucle for; en su lugar, accederá a la dirección de la variable contador i. Debido a que el valor de array[100] se pone a -10000, la variable contador se pondrá a -10000, de forma que la ejecución del bucle tomará mucho más tiempo y es posible que no termine en absoluto. De forma que el juez os da el mensaje "Límite de Tiempo Excedido", pero en realidad es un error de asignación de memoria.
• Probad el programa con varios conjuntos de datos
Siempre hay una entrada y una salida de ejemplo proporcionada con cada cuestión del concurso. Los concursantes sin experiencia que se vean incapaces de resolver ningún problema se ilusionan cuando la salida de uno de sus programas coincide con la salida ejemplo para la correspondiente entrada, y piensan que han resuelto el problema. Así que, sin malgastar ni un segundo, entregan el problema para que sea corregido y en muchos casos consiguen una respuesta de "erróneo". Un conjunto de datos no comprueba si las variables de tu programa se han inicializado correctamente, porque por defecto todas las variables globales tienen el valor cero (enteros = 0, caracteres = "\x0", reales = 0.0, y punteros = NULL). Incluso si los asignáis al principio del programa. {Incluso si usáis varios conjuntos de datos, el error puede seguir oculto si los conjuntos de datos son del mismo tamaño, a veces de tamaño decreciente o creciente}. Por tanto, el tamaño de la secuencia del conjunto de datos debería ser aleatorio. Es siempre una buena idea escribir una función separada para la inicialización.
• ¿Cómo tomar la entrada de reales en matrices?
Considerad el siguiente segmento de código:
#include <stdio.h>
float store[100];
void main(void)
{
int j;
for(j=0;j<100;j++)
scanf("%f",&store[j]);
}
Cuando este programa se ejecute, muchos compiladores de C/C++ mostrarán el error "Formato de Coma flotante no Enlazado". Para eliminar este error, tan sólo hace falta tomar la entrada en una variable normal de coma flotante, y entonces asignar dicha variable a la matriz, tal como sigue:
#include <stdio.h>
float store[100];
void main(void)
{
int j;
float temp;
for(j=0;j<100;j++)
{
scanf("%f",&temp);
store[j]=temp;
}
}
• Sugerencias de Mark Dettinger sobre los problemas de geometría
Mark Dettinger era el entrenador de la Universidad de ULM. Me sugirió que a veces es buena idea evitar los problemas de geometría a menos que uno tenga rutinas ya escritas. Las rutinas que pueden ser útiles son:
1. Intersección de dos rectas
2. Intersección de dos segmentos
3. Intersección de recta y segmento
4. Convexidad de una superficie/bóveda/curva {Casco convexo}
5. Punto interior a un polígono
6. Desde un gran número de puntos, cual es el número máximo de puntos en una sóla recta
7. El problema del par más cercano (Dado un conjunto de puntos, tenéis que encontrar el par de puntos más cercano entre ellos)
8. Tratad de aprender cómo se usa la función qsort() de C para ordenar enteros y registros.
9. El área de un polígono (Convexo o Cóncavo)
10. Centro de gravedad de un polígono (Convexo o Cóncavo)
11. Circunferencia Mínima (Para un número dado de puntos junto con sus coordenadas, encontrar la circunferencia con radio mínimo que les incluya a todos)
12. Esfera Mínima
13. Si un rectángulo entra {es interior a} en otro rectángulo (incluso rotándolo)
14. Intersección de dos circunferencias. Si no se produce la intersección, detectar la situación (si uno está dentro del otro, o si están lejos)
15. Algoritmos de recorte de rectas (contra un rectángulo, círculo, elipse).
• ¡Corregiré al juez!
Los jueces a veces omiten información que deberían haber dado. Por ejemplo, los jueces de mi país dan el error "Límite de Tiempo Excedido" pero nunca dicen cual es el límite de tiempo. En Valladolid, normalmente no se especifica el tamaño de la entrada (por ejemplo, el problema 497 - Iniciativa de defensa Estratégica). De forma que tratad de {sonsacar} a los jueces.
Suponed que no os dan el número máximo de entradas. Normalmente esto es una información vital por que si el número es pequeño, podéis usar backtracking, y si es grande, tenéis que usar técnicas como programación dinámica o backtracking con memorización. En el problema 497, no se da el posible número máximo de misiles a interceptar. Suponed que el bucle for (j=0;j<;100000000;j++) necesita 1 segundo de ejecución para el juez, y que N es el número de entradas dadas por el juez virtual, pero que no sabéis su valor. Entonces, enviad el siguiente programa con vuestro código. Ponedlo justo antes de que hayáis sabido el valor de N:
for(I=1;I<=20;I++)
{
if(I*1000>=N)
{
for(j=0;j<I*100000000;j++);
}
}
Ahora, de la ejecución de este programa podéis deducir el número de la entrada N. Usando este método también podéis determinar cuanto más rápido es el ordenador del juez que el vuestro, y así averiguar el límite aproximado de tiempo para cualquier problema en vuestro ordenador. La mayoría de los concursos en vivo tienen una sesión de práctica antes del concurso. Ese día, debéis tratar de determinar la velocidad del ordenador del juez enviando muchos programas que consistan de muchos bucles y bucles anidados.
(
La Historia del Problema de la Final Mundial del 2000:
¿Sabiaís que hubo un error en el problema de la Final Mundial del 2000?. El problema culpable era el problema F. La especificación del problema decía que el grafo de entrada debía ser completo, pero no todas las entradas del juez eran grafos completos. Uno de los equipos <;puede que otros también> enviaron un programa que comprobaba si el grafo de entrada era completo. Si el grafo de entrada era incompleto, entonces su programa entraba en un bucle infinito. De forma que la respuesta del juez era "Límite de Tiempo Excedido". De esta respuesta ellos fueron capaces de deducir que alguno de los grafos de entrada era incompleto, y resolvieron el problema de acuerdo con esto.)
• Usad doble precisión en lugar de reales simples (double en lugar de float)
Es siempre buena idea usar un 'double' en lugar de un 'float', puesto que el 'double' da más precisión y rango. Recordad siempre que existe un tipo de datos llamado 'long double'. En el C/C++ de Unix/Linux, hay también un 'long long integer', y el Juez Virtual corre bajo Linux. Algunas veces se especifica en el enunciado del problema el uso del tipo 'float'. En esos casos, usad 'floats'.
• Uso avanzado de printf() y scanf()
Aquellos que hayáis olvidado el uso avanzado de printf() y scanf(), recordad los siguientes ejemplos:
scanf("%[ABCDEFGHIJKLMNOPQRSTUVWXYZ]",&linea);
//donde linea es una cadena
Esta llamada a la función scanf() toma sólo las letras mayúsculas como entrada para la línea, y cualquier otro carácter que no sea A..Z finaliza la cadena. De forma similar, la siguiente llamada a la función scanf() se comportará igual que un gets():
scanf("%[^\n]",linea); // donde linea es una cadena
Aprended los caracteres finalizadores por defecto de la función scanf(). Intentad leer todas las características avanzadas de scanf() y de printf(). Esto os ayudará a la larga.
• Uso de nueva línea con scanf()
Si el contenido de un archivo (input.txt) es:
abc
def
y el siguiente programa se ejecuta para que tome la entrada del archivo:
char input[100],ch;
void main(void)
{
freopen("input.txt","rb",stdin);
scanf("%s",&input);
scanf("%c",&ch);
}
¿Cuál será el valor de input y ch?
Aquí tenemos una modificación del código:
char input[100],ch;
void main(void)
{
freopen("input.txt","rb",stdin);
scanf("%s\n",&input);
scanf("%c",&ch);
}
¿Cuál será su valor ahora?
El valor de ch será '\n' para el primer segmento de código, y 'd' para el segundo.
• Memorizad el valor de pi
Siempre deberíais intentar recordad el valor de pi con tantos decimales como sea posible.
3.1415926535897932384626433832795, quizá la parte en negrita. Puede que los jueces no os den el valor en la pregunta, y si usáis valores como 22/7 o 3.1416 o 3.142857, es muy posible que alguna de las entradas críticas de los jueces os den la respuesta por incorrecta. También podéis obtener el valor de pi como una constante definida por el compilador, o del siguiente código:
pi=2*acos(0);
• Problemas con la igualdad de números en coma flotante (precisión doble o simple)
No siempre podéis comprobar la igualdad de números en coma flotante con el operador == en C/C++. Lógicamente, sus valores pueden ser los mismos, pero debido al límite en la precisión y a errores de redondeo pueden diferir en una pequeña cantidad, y pueden ser considerados desiguales incorrectamente por vuestro programa. Por tanto, para comprobar la igualdad de dos números a y b en coma flotante, podéis usar un fragmento de código como el que sigue:
if (fabs(a-b)<;ERROR) printf("Son iguales.\n";
Aquí, ERROR es un valor en coma flotante muy pequeño, algo así como 1e-15. En realidad, 1e-15 es el valor por defecto que los jueces escritores de soluciones usan. Este valor puede cambiarse si la precisión se especifica en el enunciado del problema.
• Los astutos jueces...
Los jueces siempre tratan de hacer largos los enunciados de problemas fáciles y los enunciados de los problemas difíciles más cortos para hacerlos parecer muy fáciles. Por ejemplo, un enunciado de un problema puede ser: "Encontrar el área común de dos polígonos". El enunciado es sencillo, pero la solución es muy difícil. Otro ejemplo es: "Para un número dado encontrar dos números iguales cuyo producto sea igual a ese número dado". Aunque el segundo enunciado es más largo que el primero, el enunciado del segundo problema sólo pregunta encontrar la raíz cuadrada de un número, que se puede hacer usando una función predefinida del compilador.
• Usad la función assert()
Casi siempre está bien usar la función de C/C++ assert(), que está en el fichero de cabecera assert.h. Con la función assert(), podéis comprobar el valor predefinido de una variable o de una expresión en una cierta etapa de vuestro programa. Si por alguna razón, la variable o expresión no tiene el valor especificado, assert() imprimirá un mensaje de error. Echadle un vistazo a la documentación C/C++ para más detalles.
• Evitar la recursividad
Siempre es buena idea evitar la recursividad en los concursos de programación, pues la recursividad lleva más tiempo, y los programas recursivos abortan la ejecución de manera mucho más frecuente (especialmente en el caso de un {análisis}), y para alguna gente es mucho más difícil de depurar. Pero la recursividad no debería estar descartada por sistema, pues muchos problemas son muy sencillos si se resuelven recursivamente (DFS, backtracking), y hay gente a la que le gusta pensar recursivamente. Sin embargo, es un mal hábito resolver problemas de forma recursiva que pueden ser resueltos fácilmente de forma no iterativa, como por ejemplo el factorial de un número, la generación de la serie de Fibonacci, y la búsqueda primero en anchura. En los concursos de programación en vivo, no vale la pena escribir código clásico. El código clásico es {tacaño}, normalmente difícil de comprender y de depurar, aunque muestre la brillantez del programador. Como por ejemplo, el código para intercambiar dos valores, que puede ser escrito de forma clásica como sigue:
#define swap(xxx,yyy) (xxx)^=(yyy)^=(xxx)^=(yyy)
Sin embargo, en un concurso no conseguiréis puntos extra por este tipo de implementación.
• Mejorad vuestra comprensión de la probabilidad y de los juegos de cartas
Tener una buena comprensión de la probabilidad es vital para ser un buen programador. Si queréis medir vuestra comprensión de la probabilidad, resolved el problema 556 de Valladolid y {sufrid} un libro de estadística sobre probabilidad. Aprendeos teoremas de probabilidad, sucesos dependientes e independientes, y probabilidad del cara / cruz. También deberíais ser capaces de resolver los problemas comunes relativos a juegos de cartas.
• Tened cuidado al usar gets() y scanf() a la vez
Deberíais tener cuidado al usar gets() y scanf() en el mismo programa. Probadlo con el siguiente caso. El código es:
scanf("%s\n",&dummy);
gets(nombre);
Y si el fichero de entrada es:
ABCDEF
bbbbbXXX
¿Qué tendríais como valor del nombre? "XXX" o "bbbbbbXXX" (Aquí la b significa un espacio).
Sugerencias para los Jueces Online basados en UNIX y para los concursos
• Portabilidad de Funciones
No todas las funciones C/C++ disponibles en DOS lo están en UNIX. Comprobad la documentación para ver la portabilidad entre distintos sistemas operativos. Si una función es portable a UNIX, podéis usarla para resolver problemas en la página de Valladolid y del USU. Usad sólo entrada estándar y funciones de salida para tomar entradas y producir salidas.
• itoa(), la función importante que UNIX NO tiene
UNIX no soporta la útil función itoa(). Un modo de sustituir esta función puede ser:
char numstr[100];
int num=1200;
sprintf(numstr,"%d",num); // a decimal
sprintf(numstr,"%X",num); //a hexadecimal en mayúsculas
Intentad sustituir cualquier otra función que no esté disponible en UNIX/LINUX.
• Problemas con la configuración del programa de correo
Algunos problemas no serán aceptados incluso cuando estén correctamente resueltos. Tales problemas son el 371 - la función de Ackermann, el 336 - un nodo demasiado lejano, el 466 - espejo, espejo, etc... Esto se debe a que nuestros programas de correo electrónico (por ejemplo, el Outlook Express, el Eudora, etc...) rompen las líneas más largas, y estos problemas tienen líneas largas en su salida. Así que en el Outlook Express deberíais ir a Herramientas -> Opciones -> Envío -> Configuración de Envío de Texto, y cambiar la opción de {Automatically Wrap Text} de 76 (por defecto) a 132. Se pueden encontrar opciones similares en otros programas de correo. El Juez Virtual de USU tiene un impreso de entrega de programa con el que podéis enviar directamente vuestro programa sin enviar un e-mail. Recordad que el problema con los parámetros del programa de correo puede causar tanto una respuesta errónea como un error de compilación.
• ¿Qué es el error de presentación?
Los errores de presentación son errores que no están causados por errores algorítmicos ni lógicos. Hay una diferencia entre el error de presentación de los jueces virtuales y el de los jueces en vivo. Los últimos son capaces de detectar los fallos, como faltas de ortografía, palabras extra, espacios extra, etc... y diferenciarlos de los errores algorítmicos, como {coste} erróneo, decisiones erróneas, etc... Estos errores son los errores de presentación tal como los clasifican los jueces humanos. Por otro lado, los jueces virtuales comparan la salida del juez y la del concursante con la ayuda de un programa de comparación de ficheros, de forma que incluso las faltas de ortografía pueden causar una "respuesta errónea". Generalmente, cuando el programa de comparación de ficheros encuentra líneas adicionales, éstas se consideran error de presentación. Los jueces humanos, por el contrario, no suelen detectar estos errores. Pero, hoy en día, los ordenadores se van volviendo más potentes, se usan entradas de juicio más grandes y se generan archivos de salida más grandes. Por tanto, en los concursos en vivo, se usan programas juez especiales que pueden detectar errores de presentación, múltiples soluciones correctas, etc... Avanzamos hacía mejores juicios {correcciones} y hacia una mejor habilidad de programación. Estadísticas recientes de ACM
demuestran que la participación en el Concurso de Programación para Colegiados de ACM se está incrementando drásticamente y que en un futuro cercano se intensificará la competición en el concurso de programación . Así que la mejora del sistema de juicio es casi una necesidad.
• Un error común de los concursantes
Recientemente, he organizado varios concursos (en colaboración con Rezaul Alam Chowdhury y en colaboración con la UVA) y he visto cómo los concursantes cometen muchos errores tontos. El error más destacable es dar las cosas por hechas. En un problema, especifiqué que las entradas serían enteros (tal como se definen en matemáticas) pero no especifiqué el rango de entrada y muchos concursantes asumieron que el rango sería 0..(2^32-1). Pero, en realidad se dieron muchos números grandes como entrada. El tamaño máximo del fichero de entrada se especificaba de lo que uno podría asumir que era el número máximo posible. Había también algunos números negativos en la entrada (los enteros pueden ser negativos).
• Las causas de un error de compilación
El error de compilación es un error común en la página de Valladolid. Puede parecer sorprendente el compilar y ejecutar un programa, enviárselo al Juez Virtual y obtener un error de compilación. Las causas más comunes para este error son:
1. La omisión de los ficheros #include:
Algunos de los compiladores que usamos no requieren incluir los ficheros de cabecera incluso cuando usamos funciones bajo estos ficheros de cabecera. Pero el Juez Virtual nunca lo permite. Por ejemplo, algunas funciones existen tanto en math.h y en stdlib.h. Para el Juez Virtual, necesitas incluir ambos ficheros de cabecera si quieres usar dichas funciones.
2. No especificar el lenguaje correcto:
Otra causa del "Errode Compilación" es no espeficiar el lenguaje correcto. Normalmente, cuando programamos en C, usamos las facilidades disponibles en C++, y entonces especificamos el lenguaje como si fuese C y obtenemos un error de compilación. Por ejemplo, el siguiente puede ser compilado como un programa de C en nuestro entorno Dos/Windows, pero no en UNIX/LINUX (los Jueces Virtuales).
for (int i=0;i<;100;i++)
{
printf("Error de Compilación\n";
}
3. El formato de envío de los e-mail
Los e-mail enviados al Juez Virtual deberían estar en formato de texto plano. Si el tipo de e-mail es texto enriquecido o HTML, el programa no se compilará. No deberíais enviar vuestro programa como un attachment.
4. Los caracteres misteriosos
Cuando empecé a programar para Valladolid al principio, usaba Turbo C++. Después de que acabé satisfactoriamente un programa, abrí el código fuente con el Bloc de Notas, seleccioné todo el texto, lo copié y lo pegué en mi editor de correo, y después lo envié a la página de Valladolid y obtuve un error de compilación. No pude descubrir la causa. Un día, lo pegué en mi editor de correo, lo grabé como un fichero de texto, después lo abrí en mi editor de texto del DOS, y descubrí algunos caracteres misteriosos en el fichero de texto, que eran invisibles en Windows. Ya no he vuelto a tener el mismo problema. Si algunos de vosotros obtenéis un error de compilación por razones desconocidas, por favor comprobad si ésta es la razón. Así, si obtenéis un mensaje de error de compilación y no podéis descubrir la causa, comprobad si vuestro programa de correo o editor de texto está añadiendo símbolos adicionales a vuestro código.
5. El uso de funciones no portables
Los errores de compilación están causados por el uso de funciones que sólo están disponibles en DOS y no en LINUX, como strrev(), itoa(), etc...
6. El uso de comentarios de estilo del C++
El C++ permite comentarios de estilo que comienzan con //. Si el programa de correo recorta el comentario a dos líneas, podéis encontraros con un error de compilación.
Algunas sugerencias específicas para Valladolid
Las siguientes son varias sugerencias para la resolución de problemas para el Juez Virtual de Valladolid:
• Tipos de entrada en el Juez Virtual de Valladolid
Existen cuatro tipos de entrada en el Juez Virtual (Último cambio)
1. Entrada no - múltiple sin programa especial de corrección (Bandera Roja)
2. Entrada no - múltiple con programa especial de corrección (Bandera Naranja)
3. Entrada múltiple sin programa especial de corrección (Bandera Azul)
4. Entrada múltiple con programa especial de corrección (Bandera Verde)
•¿Qué es un programa de corrección especial?
Existen algunos problemas que sólo tienen una única salida para una única entrada, pero otros problemas pueden tener más de una salida para la misma entrada. Por ejemplo, si os preguntan cual es la cadena de longitud 3 que más aparece en la cadena "abcabcabcijkijkijk", desafortunadamente la respuesta puede ser tanto "abc" como "ijk". Por tanto, si vuestro programa devuelve "abc", es correcto, si devuelve "ijk" es también correcto. El programa juez no puede determinar la corrección de vuestro programa simplemente comparando vuestra salida con la del programa del juez. El juez debe escribir un programa especial, que leerá vuestra respuesta y determinará si es correcta o no. Este programa especial se describe como un programa especial de corrección en el Juez Virtual de Valladolid. Para los problemas con programa especial de corrección (Problemas 104, 120, 135, etc... o los programas con bandera verde o naranja) ni podéis estar seguros de que vuestro programa sea incorrecto incluso si la salida de vuestro programa no coincide con la salida de ejemplo para una entrada dada de ejemplo.
Los "Programas de Entrada Múltiple" son un invento del Juez Virtual. He aquí la razón por la que han nacido los programas de entrada múltiple. El Juez Virtual utiliza normalmente los problemas y los datos que se usaron en los concursos en vivo. Hay algunos problemas en los concursos en vivo cuyas soluciones toman un solo conjunto de datos, da la salida correspondiente, y termina. Esto no implica que los jueces den sólo un conjunto de datos. En realidad los jueces dan varios ficheros como entrada, uno después de otro, y comparan los correspondientes ficheros de salida con la salida del juez. Sin embargo, la política del Juez Virtual de Valladolid es diferente. Siempre prefiere dar un único archivo como entrada. Inserta todas las entradas del juez en un único fichero y en el comienzo de ese fichero escribe cuantos conjuntos de datos habrá. Este número es el mismo que el número de ficheros de entrado que usan los jueces del concurso. Una línea en blanco separa cada conjunto de datos. Por tanto, la estructura del fichero de entrada para un programa de entrada múltiple es como sigue:
integer N //que denota el número de conjuntos de entrada
--- línea en blanco ---
conjunto de entradas 1 /* como esté descrito en el enunciado del problema */
--- línea en blanco ---
conjunto de entradas 2 /* como esté descrito en el enunciado del problema */
--- línea en blanco ---
conjunto de entradas 3 /* como esté descrito en el enunciado del problema */
.
.
.
--- línea en blanco ---
conjunto de entradas N /* como esté descrito en el enunciado del problema */
--- final del fichero ---
Fijaos en que no hay línea en blanco después del último conjunto de datos (a veces puede haberla, por tanto, comprobad ambas posibilidades). La estructura de un fichero de salida para una entrada múltiple será:
salida para el conjunto 1 /* como esté descrito en el enunciado del problema */
--- línea en blanco ---
salida para el conjunto 2 /* como esté descrito en el enunciado del problema */
--- línea en blanco ---
salida para el conjunto 3 /* como esté descrito en el enunciado del problema */
--- línea en blanco ---
.
.
.
--- línea en blanco ---
salida para el conjunto N /* como esté descrito en el enunciado del problema */
--- final de fichero ---
El Juez Virtual de la USU no tiene programas de entrada múltiple como el de Valladolid. Prefiere dar múltiples ficheros como entrada y asigna un tiempo límite para cada entrada.
• Problemas de los Programas de Entrada Múltiple
Existen algunos puntos que deberíais considerar para los programas de entrada múltiple.
1. Incluso si la especificación de entrada dice que la entrada termina con el final de fichero (EOF), cada conjunto de entradas finaliza en realidad con una línea en blanco, excepto para el último, que termina con el final de fichero.
2. Tened cuidado con la inicialización de las variables. Si no se inicializan de forma correcta, vuestro programa puede funcionar para un único conjunto de datos pero dar salida correcta {incorrecta} para varios conjuntos de datos. Todas las variables globales se inicializan a sus correspondientes ceros. Así, para un único conjunto de entradas, la inicialización puede no ser necesaria, pero para múltiples entradas, es un requisito.
• La sección de "Arreglando Errores"
Aseguraos siempre de echarle un vistazo a la sección de Arreglando Errores del Juez de Valladolid. Algunos de los problemas del Juez Virtual de Valladolid tienen errores. Algunos de los errores se han corregido en esta página.
• Leer el Tablón de Mensajes
Intentad siempre leer el tablón de mensajes del sitio de Valladolid. Aprenderéis muchas cosas de otros programadores. El Juez Virtual de la USU también tiene un tablón de mensajes. Podéis también enviar vuestros propios puntos de vista y problemas por medio de estos tablones.
Conclusión
Mucha gente tiene la idea general de que aquel que conoce más algoritmos es el mejor programador. Pero como en el proverbio {"There are many a slip in between the cup and the lip"}, esta idea no es cierta. Para ser un programador mejor, necesitas tener una muy buena comprensión de las matemáticas. La resolución de un montón de problemas de matemáticas te ayudará a mejorar tu capacidad analítica, que es el rasgo más importante de un buen programador. Me he dado cuenta de que resolver tipos diferentes de problemas de geometría ayuda especialmente en la mejora de la capacidad analítica de cualquiera. Como concursantes, no debéis nunca perder los nervios durante un concurso. No podéis ser mejores programadores de lo que realmente sois, pero en el concurso deberíais intentar hacerlo siempre lo mejor que podáis.
jajaja puro copy pero sirve