SoloCodigo

NIVEL: MEDIO

Introduccion:
En este juego de ajedrez, el caballo cumple un rol un poco mas importante que solo moverse. Tiene como objetivo, juntarse con el rey, y/o llevarlo hacia algun casillero del tablero.

Descripción:
Crear un programa, que dado un tablero cuadrado de N (5 <= N <= 20) cuadraditos de lado,  K (1 <= K <= 400) caballos, su posición y la posición del rey en el tablero, determine el menor numero posible de movimientos, que permitirian a todos los caballos, juntarse con el rey.

El rey se mueve en las 8 direcciones, 4 casilleros adyacentes y los 4 diagonales.
El caballo se mueve a 8 direcciones: cada una es diferente de la inicial con 2 unidades y 1 unidad de (x, y) o (y, x). (Movimiento clasico!!)

Mas de una figura puede estar en el mismo cuadradito en un instante dado.
Estando uno o mas caballos en el casillero del rey, este puede viajar con el caballo (como se mueve el caballo).
El rey, no necesariamente tiene que viajar con caballo, eso es solo una posibilidad.
Las piezas se pueden juntar en cualquier casilla, el problema es encontrar la que menos movimientos necesitara, e imprimir en la salida esa cantidad.

Entrada (caballo.in):
En la primera linea: 2 enteros: N y K
En la segunda linea: x y (la posición del rey al inicio del juego)
Lineas 3…3+K-1: x y (la posición de cada caballo)

Salida (caballo.out):
Un solo entero: el numero de movimientos minimos que hay que realizar para lograr juntar todas las piezas del tablero en un solo casillero.

Ejemplo:

Entrada:
8 4
4 4
1 3
1 8
8 1
8 8

Salida:
10

Explicacion de la salida:
Se juntan en (2,5).
Caballo 1: 1,3 – 2,5 (1 movimiento)
Caballo 2: 1,8 – 3,7 – 2,5 (2)
Caballo 3: 8,1 – 7,3 – 6,5 – 4,4 (se lleva el rey y..) – 2,5 (4 movimientos)
Caballo 4: 8,8 – 6,7 – 4,6 – 2,5 (3)
1 + 2 + 4 + 3 = 10 moves.


P.D.1: Denle, no es tan dificil, cosa de una horita.
P.D.2: Este reto lo tengo programado para un par de semanas, pero la verdad me da lo mismo cuando se quita... depende del interes que hay hacia el.
P.D.3: Cualquier pregunta, por favor, no se la aguanten.

oye ya tengo la solucion y voy a programarla pero como el la primera vez que participo en esta seccion de retos, tengo una duda que yo creo mas bien es para juanK (el moderador). eso de salida y entrada, o sea caballo.in y caballo.out, significa que los datos para el problema deben de ser leidos de un archivo(llamado caballo.in) y la salida debe ir a dar a otro(caballo.out).

Perdon si es una pregunta boba pero como te digo es la primera vez que intento participar

hola..
aprovecho para aclarar que no es no quiera participar en los retos y que me parezcan simples..
por el conmtrario yo seria feliz haciendo todas estas cosas, pero a diferencia del año pasado hoy en dia no tengo de nada... y me toc< conformame con leer lo quie ustedes hacen.. animo!!!

Blaq, me tomo nota. Gracias.

Eso del cambio de Pascal a C, es verdad eh....
Yo programaba en Pascal, pero luego se me vino esto de las competencias de programacion, y el Pascal no esta al nivel asi que me tuve que cambiar. La verdad es que una vez que te acostumbres al C no vas a querer ni escuchar de pascal.

Lo que mas me faltaba eran los arrays con indices negativos, pero con el tiempo se supera
La verdad es que el C es mucho mas ordenado, y la sintaxis es mas facil de seguir, ademas que es mas amistoso que Pascal (ese sentimiento me dio cuando me familiarize con el)... como se le dice... user friendly

Hay un chistesito por alli de eso:
"Los programadores intentan crear mas y mas software user friendly y facil de usar. La naturaleza, por el otro lado, esta creando cada vez idiotas superiores. Por lo visto hasta ahora, la naturaleza esta ganando" --> Eso va dedicado a los programadores, todos sabemos que tienen hartos problemitas con el cliente, porque es dificil que una persona que no programe pueda entender las dificultades, como sea... me fui hacia otro cuento.

Para lo del reto... es bonito no? A mi personalmente me gusta mucho este en especial, es de las olimpiadas internacionales para alumnos de ensenianza media (secundaria). Lo que no significa que sea facil, pero tiene una solucion facil bastante trivial y facil de implementar. Eso si, el conocimiento de un algoritmo es fundamental: XXXXX XXXX. (alli les digo cual)

Saludos!

EL rey se puede mover por si solo.
El movimiento del rey con el caballo cuenta como 1 movimiento.
(Ver ejemplo de entrada y salida + explicacion)

La cosa es que hay que optimizar todos los movimientos, si eso requiere por ejemplo que el rey se mueve un cuadradito, luego se junte con un caballo y se mueva un poco mas, y luego se mueva por su cuenta, entonces eso es totalmente valido.

Espero que nadie se vaya por el backtracking, porque el tablero es bastante grande, y las restricciones son bastante limitadas

 a mi me paso igual nagisa......... asi que ahora estoy buscando otra solucion

Algo asi estaba planeando pero me fui mal por que yo comprobaba la posicion de todas las piezas casilla por casilla(yo creo por eso no me salio), pero bueno asi como dices se ve mas logico. Lo dificil creo que consistiria en el Rey por la forma en que se puede mover.

Hey esto no tiene nada que ver con el tema, pero....
En lso post que lei tuyos de retos... vi.. o me parecio, que son los de la ACM, no?

Saludos.

he leido todo el foro y el reto no se ve complicado , pero como ya dijeron algunos de los foreros el problema es de tiempo... si me queda alguito se lo dedicare al reto...   pero lo que nocreoes que el reto sea solo para desarrollarlo en dos horas..

Saludos

Este problema es sacado de IOI 1998 (International Olympiad in Informatics) que es para jovenes de secundaria. Las reglas de la IOI son 5 horas para 3 problemas, lo que impondria un limite de menos de 2 horas para cada problema.

Los problemas nunca se repiten y nunca seran de aplicar un algoritmo conocido y ya, porque eso no es la idea, sino, combinaciones y modificaciones de algoritmos, que lo harian mas dificil...

Hay personas que resuelven los 3 problemas en ese tiempo, pero la mayoria estan capaces de hacer 2 de 3, que tampoco es malo...

Yo participo en esta competencia, y en una semana estare participando en la IOI 2004 en Grecia, asi que por favor no me digan que no se pueden resolver, porque hay muchas personas que lo hacen.

10 mins para leer y entender el problema
20 mins para inventar algoritmo
30 mins para codificarlo
10 mins para depurarlo

Eso seria un tiempo normal para cualquier problema...
Saludos!

Pues, no creo que se trate de saber o no, sino que esas competencias requieren tener una practica bastante activa los ultimos 5-6 meses antes de la competencia de modo que  se te vengan ideas a la cabeza de inmediato...

En los ultimos 8 meses yo resolvi 500-600 problemas por el estilo, con eso, al ver un problema se me ocurren muchas formas de trabajarlo y asi puedo tener algoritmos entre los cuales elegir el mas apropiado...

El otro dia hice copy *.cpp y me sorprendi al ver 500 archivos copiados, que son todo mi empenio de los ultimos meses. Aun asi... creo que uno nunca esta lo suficientemente preparado para lo que viene, porque en las internacionales no dan problemas que ya se hayan visto o publicado, sino que los inventan y los dejan de modo tal que el algoritmo que hay que usar sean irreconosible... o hay que modificarlo demasiado para que se ajuste al problema.

Como sea... deseanme suerte para el 10 de sept que tengo la olimpiada y esoty nervioso Adios a todos!! Estare un buen tiempo sin posts por aqui...

Saludos desde Chile...