>> Um camelo deve fazer uma entrega de 1000 litros de água ao Sindicato dos >> Beduínos, que fica a 1000 km de distância de seu oásis de partida. O camelo >> pode carregar até 100 litros de água e deve beber (continuamente) 1 litro de >> água por quilômetro. Ele pode deixar depósitos de água em qualquer ponto do >> caminho. De quanta água (no mínimo) ele precisa para cumprir sua missão?
On Sun, Nov 16, 2003 at 10:52:34PM -0200, Fabio Dias Moreira wrote: > Tá, eu entendo o seu raciocínio, mas eu interpretei o enunciado de > maneira diferente da sua: estes reservatórios não vêm de graça e você > não pode posicioná-los arbitrariamente ao início do processo; o deserto > está inicialmente vazio e o camelo deve fazer excursões a partir de seu > oásis-base para montar estes reservatórios no meio do deserto. > Estabelecer reservatórios custa água. > > Óbvio, posso ter entendido o enunciado errado. Caso o tenha feito, a > sua solução está perfeita. Oi lista, eu tenho ficado calado sobre este problema meio por preguiça. A interpretação que o Gugu e eu tínhamos em mente é a do Fabio, se eu bem entendi o que ele disse. Inicialmente não há nenhum reservatório e nenhuma água no deserto, toda a água está no ponto de partida do camelo. O camelo pode largar um ou mais tanques de água em qualquer ponto no meio do deserto e voltar lá mais tarde para buscar a água: ninguém rouba a água, a água não estraga nem evapora. É bem óbvio (dada a interpretação correta) que o camelo precisa fazer muuuuuuuuitas viagens. Uma solução (não ótima) a seguinte: o camelo sempre pode botar nas costas até 100 litros de água, andar um quilômetro, depositar 98 litros, voltar e repetir a operação (os dois litros restantes foram consumidos pelo camelo). Assim, se queremos ter N litros de água e o camelo no quilômetro M+1 basta termos f(N) = N + 2k - 1 litros na posição M onde k é o menor inteiro maior ou igual a N/98. Assim, começando com f^1000(1000) litros conseguimos completar a missão. Fazendo as contas no maple isto dá: > f := n -> n + 2*ceil(n/98) - 1: > a[0] := 1000: > for i to 1000 do a[i] := f(a[i-1]): > od: > a[1000]; 592731741234 que *não* é a melhor resposta possível. Mas é verdade que esta coisa cresce exponencialmente e que a resposta vai ser grande. Fica como exercício para vocês procurar a solução ótima e demonstrar que ela é mesmo ótima. []s, N. ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================