SoloCodigo
Asuntos Oficiales => Retos => Mensaje iniciado por: Binary en Jueves 5 de Agosto de 2004, 06:50
-
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.
-
?! 1 dia sin que nadie lo haya resolvido? :blink:
-
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
-
Por favor, REDD, tu pregunta esta bien puesta.
Efectivamente....
Los datos te vendran en el archivo "caballo.in", de donde los leeras, los procesaras y luego escribiras tu salida en "caballo.out".
xxx.in y xxx.out es igual que manipular xxx.txt (por si las dudas)
Saludos.
-
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!!!
-
?! 1 dia sin que nadie lo haya resolvido? :huh:
¿¿¿resolvido??? :huh: Si no me equivoco....se dice Resuelto :lol:
A mi también me gustaria resolver los retos.....pero la verdad es que no tengo tiempo para nada :(
Saludos,
Blag :devil:
-
Blaq, me tomo nota. Gracias.
-
Realmente todavia no puedo sacar la sintaxis de Pascal de la cabeza, y tu reto si que es un RETO (por lo menos para mi) . Mi problema es que estoy con C hace 2 semanas y aprendí demasiado, más de lo que podría soportar y creo esto hice que me estresara un poquittitito. Estoy confusio :blink: . Aunque no fue tan dificil como supuse. Tengo que decirlo en algun lado, C es de lo mejor (no para todo) :rolleyes: .
Bueno, nos veremos el domingo para más noticias ya que mi unico tiempo para programar es el sabado a la noche o mejor dicho domingo a la mañana(01:00 hs).
-
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 :D
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 :D
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" :D --> 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. :D (alli les digo cual) :D
Saludos!
-
Waaaaaaaaaaaaaa!! Es un reto bastante curioso cuando menos... Por lo menos se sale de la clasica vuelta del caballo (Knigth's Tour creo que se le llama en ingles).
Tengo una duda. El rey puede moverse tambien?? Digo solo y por si mismo con el movimiento clasico del rey (una casilla en cualquier direccion). Y otra mas... Si el rey se mueve con caballo, cuenta solo un movimiento, no??
Si puedo me pondre con el, aunque no creo por que tengo mucho que estudiar (9 para Septiembre y encima trabajo de 14:00 a 21:00) T__T Mi gcc me hecha de menos.... Aunque me vendria bien para el concurso de programacion de Octubre...
See ya!!
-
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 :D
-
La verdad que mi primera (y lamento decir que unica) idea gue backtracking... Pero pronto descubri que era demasiado mala!! Asi que ahora mismo estoy asi: :alien:
esperare a que postees la solucion para reirme de lo tonto que he sido :lol: , o no....
-
:P a mi me paso igual nagisa......... asi que ahora estoy buscando otra solucion
-
Pues... la solucion no es sencilla, requiere saber un algoritmo en especial, por algo dice nivel medio y no facil...
A ver, dejenme dejarles una pista que se me murieron con este reto:
Es cosa de buscar soluciones chicas, como para poder armar todo el cuento despues. Por ejemplo: calcular la cantidad de movimientos que tomaria el rey en llegar a todos los cuadraditos, calcular la cantidad de movimientos que le tomaria a cada caballo llegar a cada cuadradito, y teniento eso, empezar a armar la respuesta de alguna manera.
Lo que pasa es que este problema puede ser separado en sub-problemas y de alli sacar una solucion. La idea va por el denominado dinamic-programming, que tiene como base la creacion de una solucion a partir de soluciones mas chicas.
Vayanlo pensando asi.
Saludos!
-
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.
-
Claro, eso seria la mayor parte del reto...
REDD, te dare otra pista... crea 400 tableros 20x20 (para cada caballo) y 400 tableros 20x20 mas para almacenar lo que le tomaria al rey ir a cada cuadradito, con ayuda de un caballo.
Miremoslo asi... el maximo caballos que pueden haber en el tablero son 400 (20x20) (Full house :D). No tiene sentido que el rey, una vez subido a un caballo, se baje y tome otro, porque igual el caballo que lo llevaba tendra que ir al punto de encuentro, asi que no le cuesta nada llevar el rey tambien.
Ahora.... hagamos asi:
int d[400][20][20]
int k[400][20][20]
d[c][j] nos da la cantidad de movimientos que le tomaria al caballo 'c' llegar a la pocision (i, j)
k[c][j] nos da la cantidad de movimientos que le tomaria al 'REY' y el caballo 'c', llegar a la posicion (i, j)
Una vez calculado todo eso... la respuesta seria:
min( para cada x, y --> min( para cada 'c' != c2 --> Suma( d[c][y]
En palabras, eso seria, que comprobemos para cada cuadrito (y, x), cuanto le tomaria a cada caballo 'c' (excepto el caballo c2) llegar a (y, x) , sumarlos, y sumar la cantidad de movimientos que le tomaria al caballo c2 llegar trayendo el rey.
Por alli va la solucion.
Todavia me imagino que esta algo borrosa, pero la vamos a ir aclarando... :D
-
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.
-
No te capto...
Si te refieres a los problemas, son de olimpiadas para alumnos de secundaria.
Son de olimpiadas como la IOI.
-
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
-
tampoco lo creo.
solo se desarrolla en 2 horas si entregan ya el algoritmo o los algoritmos que hay que usar , es decir si es solo hacer el programa..
porque si toca deducior el algoritmo o buscarlo y luego entenderlo.,.. nadie lo puede hacer en ese tiempo.
-
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!
-
:( Siempre lo he dicho...
soy un completo tonto :(
Yo tambien he participado en competencias de programacion y es cierto los tiempos que dan por lo general son esos, aunque yo nunca he estado en competencias internacionales.
Creo que hace falta ser un genio o tener mucho de genio para sacar muchos de esos algoritmos en el tiempo que se piden, conozco algunos de la universidad de los andes que si lo hacen... pero yo.. por lo menos en el momento no tengo la fortuna de poder deducir y entender un algoritmo tan rapido como se requiere en esta prueba que has posteado. :adios:
-
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...
-
Buena suerte bynary!!!
recuerda que con el simple hecho de asistir a un evento de esos tu ya eres un ganador!!!.
-
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 :D
:huh:
-
No conoci mucho pascal,
peo creo que c es mucho mejor y la sintacis me gusta más, claro que esto se puede deber a que no manejo ese lenguaje.
-
puedo hacer el programa pero lo que no se es jugar ajedrez , estoy en eso por que no le entiendo a lo de N(20<= ) y no se que mas , dejenme que aprenda ajedrez y luego trato de resolver el reto :) .
haber el tablero es de 20 x 20 , osea de 400 cuadros , pero la K que significa ?? que el caballo puede estar en cualquiera de los 400 cuadros??? , ademas cuales son las posiciones iniciales de el rey y de el caballo??.
-
Hi everyone... im back...
Luego de mi presentacion en Athenas el 11-18 de septiembre, me fui a Bulgaria, mi pais natal, donde estuve por 1 mes, asi que ahora estoy de vuelta...
Sin medalla de las internacionales, pero igual, feliz de haber ido...
grrrr... 255/600 ptos finales... 265 era bronce, no importa... es mas impiortante participar que ganar (el logo de los perdedores), pero ahora le encuentro el sentido...
Bueno... no tengo mucho tiempo, encontre mi PC con un monton de viruses, asiq ue voy a reinstalarlo, luego vere que mas hago...
Adios...
-
:comp: :lol: Muy bien Bynary te felicito!!!
bienvenido de regreso al foro. :smartass: