Cinco pessoas precisam atravessar uma ponte numa noite escura, porém, só tem uma lamparina com duração de 30 minutos. Cada uma das pessoas tem um tempo de travessia diferente, e nenhuma consegue atravessar sem iluminação. A ponte só aguenta, no máximo, duas pessoas por vez. Desenvolva um algorítmo que permita a travessia de todos, considerando os seguintes tempos de travessia:
Passo 1
Eai, doido! Olha, vamo começar lembrando que não existe somente uma solução, beleza? Vou te contar uma delas, mas você pode ter uma ideia diferente, até melhor! Fazer igual a mim não é uma regra, ok?
Show! A lâmpada ainda tem 30 minutos de duração. Quem vamos atravessar primeiro?! Eu escolhi atravessar primeiro os dois caras que têm os menores tempos de travessia (1 e 3).
Como ninguém consegue atravessar no escuro, o mais rápido teve que vir no ritmo do cara mais lento. Ou seja, a travessia durou 3 minutos. Com isso, a lâmpada ainda tem 27 minutos de duração. Agora a gente precisa que alguém volte pra buscar outra pessoa. Vamos pro próximo passo então!!
Passo 2
Agora, eu pode ser uma boa a gente voltar com o cara mais rápido, mas na verdade, não faria diferença. Você logo vai ver o porquê.
Agora, a gente pode fazer a seguinte malandragem: deixamos as duas pessoas mais lentas atravessarem juntas, assim eliminando uma viagem demorada. Deixa eu te explicar melhor.
Por exemplo, imagine que o maluco rapidão vá com a senhora de 12 minutos, depois volte, depois vá com a de 8. Essas 3 viagens vão levar 21 minutos no total. Agora, se elas forem juntas, vai levar 12 minutos. Viu? Se as pessoas mais lentas forem juntas, no fim, vai economizar tempo.
Agora, vamos ao próximo passo!
Passo 3
Agora tu já deve ter se ligado no porquê eu quis levar o maluco de 3 minutos primeiro. Olha, agora ele consegue voltar com a lâmpada em 3 minutos pra ajudar o resto da galera! E outra coisa, se eu tivesse primeiro voltado com o maluco de 3 minutos, agora teria que voltar com o de 1 minuto. Ou seja, não faria diferença, beleza?
Show! A gente volta com o doido de casaco:
Ainda nos resta 11 minutos de energia na lâmpada. Repara que os dois mais rápidos estão do mesmo lado, e a gente vai precisar voltar depois. Por isso, é uma boa ideia a gente mandar o mais lento com o mais rápido, pra que o mais rápido consiga economizar tempo na volta.
Ainda nos resta 5 minutos. Mas o maluco rapidão consegue voltar em 1. Então vamos ao próximo passo.
Passo 4
Cara, agora a gente só precisa buscar o doido de casaco que ficou sozinho do outro lado. O Usain Bolt ali vai fazer isso pra gente.
Agora temos 4 minutos restantes. Porém, a travessia desses dois malucos juntos dura só 3 minutos. Com isso, resolvemos nosso problema!!!
Ainda nos restou 1 minuto de bateria. Ufa! Salvamos todo mundo! Hahaha
Valeu, carinha! Até a próxima aventura!
Resposta
- Atravessa A e B
- Volta com A
- Atravessa D e E
- Volta com B
- Atravessa A e C
- Volta com A
- Atravessa A e B