Problema FINAL ANPA 08. Pirámides Limogochianas

Hola a todos!

Les presentamos  uno de los problemas de la final del Abierto Nacional de Programación Ants 2008. Agradecemos a Darkmars por su aportación.

Historia

Como todos sabemos, los limogochis construyen pirámides meramente por ociosidad. Una pirámide limogochiana, es una pared de ladrillos de ancho uno y base l, los siguientes niveles se construyen poniendo un ladrillo entre cada ladrillo del nivel anterior. Por razones estéticas les impar.

Como la construcción no es totalmente inútil (podría ser que el muro sirviera para algún propósito inesperado), los limogochis se dan a la tarea de numerar cada ladrillo. Primero, numeran los ladrillos de la base del 1 a l (afortunadamente , en orden creciente). Cada ladrillo, de un nivel superior a la base, es marcado con la suma de los ladrillos que se encuentran justo debajo del ladrillo en cuestión.

Problema

Dada l,determinar el valor residuo rque deja el número escrito en la punta de la pirámide al dividirse entre m.

Entrada

La primera línea tiene un único valor entero nque indica el numero de casos de prueba. Cada caso de prueba consta de una línea con dos enteros (separados por un espacio) 0 < l< 50,000 y 0< m< 65,536 respectivamente. Los casos de prueba están separados por una línea en blanco.

Salida

El archivo consta de n líneas, cada línea con un único valor entero r que representa el residuo que deja el número de la punta de la pirámide limogochiana entre el número m.

Problema 3-Repechaje. El misterio de la ecuación

Hola a todos!

Les presento el tercer problema del repechaje. Pronto los problemas de la final.

Les recuerdo que el sistema de competencia ha cambiado!

El misterio de la ecuación

Historia

Juanito ha entrado a la primaria y las reglas parecen ser muy estrictas. Por ejemplo en su clase de matemáticas su maestra le ha pedido que debe escribir las ecuaciones con dos colores de tinta (azul y rojo). Pero Juanito perdió su pluma azul entonces ha decidido copiar solo los números de sus ecuaciones y después reconstruir las ecuaciones. Se ha dado cuenta que no es una tarea tan fácil y ha solicitado tu ayuda. Los signos que le faltan a las ecuaciones son 5 (suma, resta, división, multiplicación e igualdad).

 

Entrada

La primera contiene el número de casos (1 <= N <= 10). La siguientes N líneas contienen 3 números positivos menores que 1000 separados por espacios.

 

Ejemplo:

2

5 6 1

1 2 3

Salida

Para cada caso imprime la ecuación válida, que incluya un signo de igualdad. Se garantiza que existe al menos una solución, en caso de múltiples soluciones cualquiera es válida.

Ejemplo:

5 = 6 – 1

1 + 2 = 3

Problema 2-Repechaje. Primos y más primos

Hola a todos!

Les presento el segundo problema del repechaje.

Primos y más Primos

Historia

Los números primos fueron estudiados en la antigüedad por razones filosóficas. Hoy en día son usados en aplicaciones prácticas, especialmente los números primos grandes son usados en criptografía. Hay un número infinito de primos conocidos, sin embargo, el número primo más grande que se conoce es un número primo de Mersenne. Se dice que N es un número primo de Mersenne cuando N tiene la forma especial 2p – 1, donde P es también un número primo. Por ejemplo 7 es un número primo de Mersenne ya que 23 – 1 = 7, y tanto 3 como 7 son números primos. Sin embargo, 2047 no es un número primo de Mersene porque aunque podemos darle la forma 211 – 1 = 2047 y 11 es un número primo, 2047 = 23 * 89.

Entrada

La primera línea contiene el número de casos M (1 <= N <= 1000). Después las siguientes M líneas contienen un numero N del cual se tiene que decir si es primo de Mersenne.

1 ≤ N ≤ 1000.

 

 

Ejemplo:

2

7

2 0 4 7

Salida

La palabra SI o NO dependiendo si es número primo de Mersenne o no.

Ejemplo:

SI

NO

Problema1-Repechaje. Plataformas Petroleras

Hola a todos!

Les presento uno de los problemas del repechaje.

Plataformas Petroleras

Historia

Uno de los mayores problemas de PEMEX durante la temporada de huracanes en el 2007 fue, el no poder evacuar todas sus plataformas petroleras antes de la llegada del huracán, con lo que sus empleados corrieron riesgos innecesarios. Para poder crear un plan de contingencia mucho más exacto, el gobierno de México está tratando de calcular el tiempo mínimo aproximado de evacuación cada una de sus plataformas.

 

Cada plataforma estará representada en forma de plano cartesiano, estando localizados todos los empleados en el cuadrante I. Cada posición puede ser utilizada solamente por un empleado a la vez. Para hacer el cálculo de tiempo se aproximó que cada persona recorre una unidad de distancia en 1 segundo por lo que a cada movimiento en X o Y en el plano cartesiano se suma una unidad de tiempo al tiempo total. El objetivo para que la evacuación se lleve a cabo en el menor tiempo posible es colocar a todos los empleados en una sola línea en el eje de las Y, sin importar la posición de la línea en X (siempre y cuando todos los empleados estén separados por solo una unidad en X) para que el helicóptero pueda recogerlos. Esta línea debe ser formada usando el menor número de movimientos posibles, para minimizar el tiempo.

 

Nota: La línea puede estar en la Y que elijas, de tal manera que esto minimice el tiempo de evacuación, de la misma manera elige X en la que inicia la línea. Cada empleado debe estar separado por solamente una unidad en el eje d las X.

Entrada

Se inicia con un número P, que es la cantidad de plataformas petroleras de las cuales se va a hacer el cálculo (1 <= P <= 10). Para cada plataforma se tiene una línea con el número E, de empleados que se encuentran en la plataforma (1 <= E <= 1000), seguido de E pares ordenados de enteros de la forma X Y que representan las coordenadas en las que cada empleado realiza su trabajo (0 <= X, Y <= 10000).

 

Ejemplo:

2

3

0 0

0 1

0 2

4

1 0

2 0

4 0

5 0

 

Salida

Para cada caso imprime el número mínimo de segundos para el ordenamiento de los empleados.

Ejemplo:

4

2

 

Equipo Técnico ANPA 09

Hola a todos

Por último les presentamos a Joemmanuel Ponce Galindo, que es pieza fundamental en este concurso.

Joemmanuel Ponce Galindo

Actualmente Coordinador Operativo de Grupo Ants México, y líder del Comité Científico del Abierto Nacional de Programación Ants (ANPA). Fue presidente de Grupo Ants de diciembre de 2007 a diciembre de 2008. Entre sus cargos en el grupo fue Coordinador de Proyectos de enero de 2007 a diciembre de 2007 y Analista de Software de julio de 2007 a noviembre de 2007. Actualmente estudia la carrera de Ingeniería en Tecnologías Computacionales en el Instituto Tecnológico y de Estudios Superiores de Monterrey.

Entre sus áreas de interés se encuentran Análisis de Modelos de Negocios e Innovación,  Programación, Algoritmos, Diseño de Software y Desarrollo Web.

Representó a México en la Olimpiada Internacional de Informática del 2005 en Nowy Sacz, Polonia. Obtuvo Medalla de Bronce en la competencia Iberoamericana de Informática por Correspondencia de 2005  organizada por Argentina.  También ganó un Primer lugar en la Olimpiada Mexicana de Informática de 2004 en Michoacán y fue el  primer lugar en la Olimpiada de Informática del Estado de Guanajuato de 2004.

saludos

Equipo Técnico ANPA 09

Hola a todos

Les presento a nuestro problem setter que está estudiando actualmente su Doctorado en la Universidad  de Tennessee.

Edgar Alfredo Dueñez Guzmán
Egresado de la Licenciatura de Matemáticas de la Universidad de Guanajuato de agosto de 1999 a julio de 2004. Graduado de la maestría de Ciencias Computacionales y Matemáticas  Industriales del Centro de Investigación en Matemáticas (CIMAT), de agosto de 2004 a julio de 2005. Actualmente se encuentra cursando su Doctorado en Ciencias Computacionales e Ingeniería Eléctrica en la Universidad de Tennessee en Knoxville desde agosto de 2005.

Entre sus logros se encuentra haber sido el primer lugar local de la Universidad de Tennessee en la competición TopCoder en 2006. Primer lugar local y segundo lugar regional en la International Collegiate Programming Constest, ACM región México –América Central en 2002. Primer lugar en la décimo primera Olimpiada Nacional de Matemáticas en Monterrey en el año 1997 y posteriormente obtuvo una medalla de plata en la décimo tercera Olimpiada Iberoamericana de Matemáticas y fue parte del equipo mexicano en la cuadragésima Olimpiada Internacional de Matemticas.

En su experiencia didáctica se encuentra haber sido aydante de cátedra para el curso Introducción a las Computadoras y  Cómputo en Knoxville, también para Algoritmos y Programación, e Introducción al Computo en la Facultad de Matemáticas de la Universidad de Guanajuato. Ha sido entrenador del equipo de Guanajuato en la Olimpiada de Informática.

Además es uno de los autores del libro Los Dilemas de Karel” (Editorial CIMAT, 2006). Ha publicado diversos artículos como “Dynamics of alliance formation and the egalitarian revolution” y “The Baldwin Effect as an Optimization Strategy”.

Confirma tu hospedaje

Hola a todos

Les recordamos que si quieren hospedarse en el hotel sede Fiesta Inn,envíenos un correo a la brevedad para apartar sus cuartos y no tengan problemas de hospedaje.

Es de suma importancia que nos envíen su confirmación a más tardar antes de que termine marzo.

Escribanos a :amaury.vega@anpa.com.mx

Saludos