Cuatro personas en un puente desvencijado

Pregunta: Cuatro personas necesitan cruzar un puente destartalado de noche. Desafortunadamente, tienen una antorcha y el puente es peligroso para cruzar sin una antorcha. El puente puede soportar solo dos personas a la vez. No todas las personas tardan lo mismo en cruzar el puente. Tiempo para cada persona: 1 min, 2 min, 7 min y 10 min. ¿Cuál es el menor tiempo necesario para que los cuatro crucen el puente?

Respuesta = 17 minutos

Solución:

La solución inicial en la que pensará la mayoría de la gente es utilizar a la persona más rápida como ujier para guiar a todos a cruzar. Pero tomaría más tiempo ya que 10 + 1 + 7 + 1 + 2 = 21 minutos. Pero, ¿puede ser la respuesta correcta? No. Eso haría que esta pregunta fuera demasiado simple, incluso como pregunta de calentamiento.

Hagamos una lluvia de ideas un poco más. Para reducir la cantidad de tiempo, debemos encontrar una manera de que 10 y 7 vayan juntos, ya que son los más lentos de todos. Si se cruzan, entonces necesitamos que uno de ellos regrese a buscar a los demás. Eso no sería lo ideal. ¿Cómo solucionamos eso? Tal vez podamos tener a 1 esperando al otro lado para traer la antorcha. Esto nos acerca a la solución. Así que vamos a poner todo esto junto.

Pasos:
1 y 2 cruzan el puente y pasan al otro lado.
Ahora 2 regresa con la antorcha desde el otro lado.
7 y 10 cruzan el puente y 2 quedan sólo para este lado.
Ahora vuelvo 1 con la antorcha del otro lado.
Por fin, 1 y 2 cruzan el puente y terminamos.

Tiempo total empleado = 2 + 2 + 10 + 1 + 2 = 17 minutos

Este artículo es una contribución de Ayush Govil . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.