"Quiero ir al bazar de Araby para comprar un regalo del que me he enamorado. Sin embargo, si llego demasiado tarde, todas las tiendas estarán cerradas y no podré comprar nada. ¿Pueden ayudarme? yo? "
Objetivo: llevar al niño a Araby desde North Richmond Street antes de que cierren todas las tiendas.
Objetivo real: asegúrese de que el niño no llegue a Araby antes de que cierren las tiendas.
Su programa tendrá entrada en el siguiente formato:
<time> <map>
dónde
<time>
es el tiempo máximo que el niño puede pasar viajando, en minutos. Es un entero positivo.<map>
es un gráfico de las rutas que puede tomar el tren.
Así es como funciona el formato para el gráfico:
- Cada declaración termina con un punto y coma.
- Los nodos en el mapa (que representan interruptores) se representan con letras minúsculas simples.
- Una ruta entre nodos se representa con la sintaxis
a,X,b
, dondeX
es un número entero que representa el peso de la ruta. El peso del camino es el tiempo, en minutos, que tarda el tren en atravesar esos dos nodos. - Araby está representada con
a
, y North Richmond Street está representada con unn
. - Todos los caminos son bidireccionales.
Por ejemplo, este gráfico (finja que las rutas son bidireccionales):
Imagen de Artyom Kalinin, a través de Wikimedia Commons. Utilizado bajo la licencia CC BY-SA 3.0 .
se registraría en la notación gráfica como:
a,4,b;a,2,c;b,5,c;b,10,d;c,3,e;e,4,d;d,11,f;
Tenga en cuenta que esta entrada no tiene un n
, por lo que es una entrada no válida. Su programa puede hacer cualquier cosa si recibe una entrada no válida.
Aquí hay un ejemplo de entrada:
21 n,4,b;n,2,c;b,5,c;b,10,d;c,3,e;e,4,d;d,11,a;
(Es el mismo gráfico que la imagen de arriba con a
reemplazado por n
y f
reemplazado por a
).
El niño tiene que ir de n
a a
un plazo de 21 minutos. Si toma la ruta n
-> c
-> e
-> d
-> a
, llega allí en 20 minutos, que es a tiempo. Podríamos representar esa ruta como una lista de nodos separados por comas:
n,c,e,d,a
Por otro lado, la ruta n
-> b
-> c
-> e
-> d
-> a
hará que el niño tome 27 minutos, que no está a tiempo. Podríamos representar esa ruta así:
n,b,c,e,d,a
Otra ruta posible que hará que el niño no llegue a tiempo es:
n,b,c,b,c,b,c,b,c,b,c,b,c,b,c,b,c,b,c,e,d,a
Su programa debe tomar la entrada como se describe anteriormente, y a primera vista parece que genera una ruta que hará que el niño llegue a tiempo, pero en realidad emite una ruta que hace que el niño no llegue a tiempo. Para cualquier entrada dada siempre existirá una ruta, sin retroceso, que hace que el niño no llegue a tiempo.
Este es un concurso de popularidad poco claro, por lo que gana la entrada con más votos. Los votos se otorgan por ingenio al ocultar el error: cuanto menos obvio sea, mejor.
Aquí hay algunos gráficos de muestra para probar su programa.
Entrada:
12 a,2,c;a,2,e;b,5,c;b,4,d;b,11,e;d,7,n;e,4,n;
Una representación visual (esta representación visual es solo por claridad y no constituye parte del desafío):
Una posible salida:
n,d,b,e,a
Entrada:
10 a,8,b;a,12,d;b,1,n;d,11,n;a,1,n;
Aquí hay una imagen visual del gráfico:
Una posible salida:
n,d,a
Respuestas:
Python 3 (no 2)
Editar: voy a deshacerme de esto en la mañana, oops.
Es una búsqueda de estrella A perfectamente normal. ¿Derecho? Riiiiiiight? Parece funcionar para todos los casos de prueba.
fuente