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