Re: [obm-l] O problema do camelo

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxxxx>]

>> 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
=========================================================================