Dick Vigarista e Muttley já estão exaustos. Em sua longa busca por pegar o Pombo a dupla seguiu por kilômetros, até alcançar um castelo assustador, com duas grandes torres. Eles, então, entram na primeira torre. Depois de um tempo investigando, sons estrondosos começam a ecoar pelas paredes, e canos parecem estremecer a estrutura do castelo... "Que tipo de castelo é esse?" "Que sons são esses??" Dick então se depara com um esqueleto no chão, ele parece ter morrido segurando uma folha de papel. Ao ler o que estava escrito na folha, Dick finalmente percebe: "OH NÃO, ESSE CASTELO É UMA ARMADILHA DO POMBO, PRECISAMOS FUGIR-" No papel estava escrito que um veneno mortal corria dentro das paredes do castelo, e irá ser liberado em 30 minutos pelo Pombo. Porém existe uma chance de sobrevivência, o texto no papel descreve a existência de válvulas (que liberariam a pressão do gás para a parte externa) espalhadas pelo castelo, tanto quanto os caminhos secretos que levam de uma válvula a outra (o input do problema). Cada válvula possui uma certa quantidade de fluxo de ULPG ( Unidades Legais de Pressão de Gás ) que ela libera por minuto jogando para fora do castelo, e caminhos secretos para outras válvulas específicas. Por exemplo, se no papel tivesse escrito: Válvula AA tem fluxo de 0 ulpg/min; passagens secretas para válvulas DD, II, BB Válvula BB tem fluxo de 13 ulpg/min; passagens secretas para válvulas CC, AA Válvula CC tem fluxo de 2 ulpg/min; passagens secretas para válvulas DD, BB Válvula DD tem fluxo de 20 ulpg/min; passagens secretas para válvulas CC, AA, EE Válvula EE tem fluxo de 3 ulpg/min; passagens secretas para válvulas FF, DD Válvula FF tem fluxo de 0 ulpg/min; passagens secretas para válvulas EE, GG Válvula GG tem fluxo de 0 ulpg/min; passagens secretas para válvulas FF, HH Válvula HH tem fluxo de 22 ulpg/min; passagem secreta pra válvula GG Válvula II tem fluxo de 0 ulpg/min; passagens secretas para válvulas AA, JJ Válvula JJ tem fluxo de 21 ulpg/min; passagem secreta pra válvula II Todas as válvulas começam inicialmente fechadas, e Dick no momento está na válvula AA, mas ela não tem fluxo nenhum, então nem vale a pena abrir. Então Dick pode passar pela passagem secreta (leva 1 minuto para atravessar uma passagem) e ir para a válvula BB, e abrí-la (também leva 1 minuto para abrir uma válvula). Agora a válvula BB estará aberta pelos próximos 28 minutos, resultando em uma liberação de 364ulpg (28 * 13 = 364). Agora pode-se ir para a válvula CC, gastando mais um minuto, e abrindo ela, gantando mais um minuto, e liberando 52 ulpg ( 26 * 2 = 52 )... Dick agora tem alguma esperança de que seja possível escapar da armadilha do Pombo, porém ele não faz a menor ideia de como ele pode fazer isso nos 30 minutos da melhor forma possível. Nessa caso, a melhor sequência de decisões seria: == Minuto 1 == Nenhuma válvulas está aberta. Dick se move para válvula DD. == Minuto 2 == Nenhuma válvula está aberta. Dick abre a válvula DD. == Minuto 3 == Válvula DD está aberta, liberando 20 ulpg. Dick se move para válvula CC. == Minuto 4 == Válvula DD está aberta, liberando 20 ulpg. Dick se move para válvula BB. == Minuto 5 == Válvula DD está aberta, liberando 20 ulpg. Dick abre a válvula BB. == Minuto 6 == Válvulas BB e DD estão abertas, liberando 33 ulpg. Dick se move para válvula AA. == Minuto 7 == Válvulas BB e DD estão abertas, liberando 33 ulpg. Dick se move para válvula II. == Minuto 8 == Válvulas BB e DD estão abertas, liberando 33 ulpg. Dick se move para válvula JJ. == Minuto 9 == Válvulas BB e DD estão abertas, liberando 33 ulpg. Dick abre a válvula JJ. == Minuto 10 == Válvulas BB, DD, e JJ estão abertas, liberando 54 ulpg. Dick se move para válvula II. == Minuto 11 == Válvulas BB, DD, e JJ estão abertas, liberando 54 ulpg. Dick se move para válvula AA. == Minuto 12 == Válvulas BB, DD, e JJ estão abertas, liberando 54 ulpg. Dick se move para válvula DD. == Minuto 13 == Válvulas BB, DD, e JJ estão abertas, liberando 54 ulpg. Dick se move para válvula EE. == Minuto 14 == Válvulas BB, DD, e JJ estão abertas, liberando 54 ulpg. Dick se move para válvula FF. == Minuto 15 == Válvulas BB, DD, e JJ estão abertas, liberando 54 ulpg. Dick se move para válvula GG. == Minuto 16 == Válvulas BB, DD, e JJ estão abertas, liberando 54 ulpg. Dick se move para válvula HH. == Minuto 17 == Válvulas BB, DD, e JJ estão abertas, liberando 54 ulpg. Dick abre a válvula HH. == Minuto 18 == Válvulas BB, DD, HH, e JJ estão abertas, liberando 76 ulpg. Dick se move para válvula GG. == Minuto 19 == Válvulas BB, DD, HH, e JJ estão abertas, liberando 76 ulpg. Dick se move para válvula FF. == Minuto 20 == Válvulas BB, DD, HH, e JJ estão abertas, liberando 76 ulpg. Dick se move para válvula EE. == Minuto 21 == Válvulas BB, DD, HH, e JJ estão abertas, liberando 76 ulpg. Dick abre a válvula EE. == Minuto 22 == Válvulas BB, DD, EE, HH, e JJ estão abertas, liberando 79 ulpg. Dick se move para válvula DD. == Minuto 23 == Válvulas BB, DD, EE, HH, e JJ estão abertas, liberando 79 ulpg. Dick se move para válvula CC. == Minuto 24 == Válvulas BB, DD, EE, HH, e JJ estão abertas, liberando 79 ulpg. Dick abre a válvula CC. == Minuto 25 == Válvulas BB, CC, DD, EE, HH, e JJ estão abertas, liberando 81 ulpg. == Minuto 26 == Válvulas BB, CC, DD, EE, HH, e JJ estão abertas, liberando 81 ulpg. == Minuto 27 == Válvulas BB, CC, DD, EE, HH, e JJ estão abertas, liberando 81 ulpg. == Minuto 28 == Válvulas BB, CC, DD, EE, HH, e JJ estão abertas, liberando 81 ulpg. == Minuto 29 == Válvulas BB, CC, DD, EE, HH, e JJ estão abertas, liberando 81 ulpg. == Minuto 30 == Válvulas BB, CC, DD, EE, HH, e JJ estão abertas, liberando 81 ulpg. Essa estratégia é a que maximiza a quantidade de ulpg liberado nesses 30 minutos, 1651!!! Ajude Dick Vigarista e Muttley a sobreviver, e descubra qual é a melhor estratégia para abrir as válvulas! Seguindo a melhor estratégia possível, quantos ulpg serão liberados?