Re: [obm-l] O problema do camelo

[Fabio Dias Moreira <fabio.dias.moreira@xxxxxxxxxxxx>]

On 11/16/03 21:03:05, Eduardo Casagrande Stabel wrote:
> [...]
> Se a pergunta �: quanta �gua ele precisa *no total* para cumprir sua
> miss�o?
> 
> Ainda assim, o problema n�o tem solu��o. Seja eps > 0. Dispomos os
> postos
> com uma quantidade de gasolina de forma que o camelo chegue at� "eps"
> quil�metros do objetivo final, com exatamente 100 litros de �gua.  
> [...]

Isso exige que se monte um reservat�rio na posi��o 1000-eps, j� que a  
capacidade m�xima do camelo � exatamente 100 (i.e. a �gua que ele leva  
� rec�m-obtida).

>                                                             [...] Ele
> vai
> at� o seu objetivo e despeja (100 - 2*eps) litros de �gua e ainda tem
> eps
> consigo, ent�o ele volta eps/2 quil�metros, se reabastece, [...]

Mas se reabastece aonde? Voc� n�o falou nada de reservat�rios na  
posi��o 1000 - eps/2.

>                                                            e retorna
> ao
> final. Dessa forma (se bem organizado) ele pode ter precisado andar
> exatamente 1000 + eps quil�metros, consumido 1000 + eps litros de  
> �gua
> e
> levado 100 litros at� o final, tendo utilizado 1100 + eps litros de
> �gua. [...]

Mas ainda faltam 900 litros. O camelo deve transportar 1000 litros, e  
n�o apenas 100.

Eu sei demonstrar que a tarefa � poss�vel por indu��o: seja d a  
dist�ncia que o camelo deve percorrer. � obvio que para d = 1 a tarefa  
� poss�vel. Suponha que � poss�vel faz�-la com V litros. Ent�o de uma  
dist�ncia d+1, basta "empurrar" 98 litros de cada vez at� a dist�ncia  
d, de tal forma que haja pelo menos V litros de �gua em d, logo agora �  
poss�vel concluir a tarefa.

Eu acho que a solu��o passa por alguma id�ia deste g�nero, com um  
incremento apropriado. Eu conjecturo que o incremento que d� o meior  
rendimento � 25.

[]s,

-- 
F�bio "ctg \pi" Dias Moreira
GPG key ID: 6A539016BBF3190A (available at wwwkeys.pgp.net)

PGP signature