Re: [obm-l] Problema do Camelo - solucao

["Rogerio Ponce" <rogerio_ponce@xxxxxxxxxxx>]

Problema do Camelo :

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?

-------------------------------
Obs:

1- O que se pretende é : qual o total mínimo da água necessária , no oásis 
de partida , para as sucessivas idas e vindas , alcançando pontos cada vez 
mais distantes, de forma a finalmente totalizar o transporte dos 1000 litros 
a 1000 km de distância.

2- O camelo só precisa LEVAR a água , isto é , não precisa fazer a última 
viagem de volta.

-------------------------------
Solução:


Chamemos o ponto inicial de INI e o final de FIM.
Cada ponto , entre INI e FIM , que vá servir como ponto de reabastecimento , 
chamaremos de "base intermediária" , ou simplesmente BASE . Claro que para 
servir como ponto de reabastecimento, em algum momento o camelo lá deixará 
alguma quantidade de água.

### Reorganização da política ###

Sejam A e B duas bases consecutivas , ao longo do caminho. Pois todas as 
trajetórias que passam entre A e B (idas e vindas) podem ser segmentadas em 
um ponto P intermediário qualquer , sem nenhum custo extra , de forma que 
essa nova base pode acumular , numa 1a. fase , toda a água que seria levada 
para mais adiante, e , numa 2a. fase essa base servirá como novo ponto 
inicial para a finalização do processo global.

ORIGINAL:

|A|--------1------->|B|
|A|<-------2--------|B|
.
.
|A|--------3------->|B|

SEGMENTADO:

|A|---1-->|P|---4-->|B|
|A|<--2---|P|<--5---|B|
.
.
|A|---3-->|P|---6-->|B|



Repare que o custo do transporte é proporcional ao comprimento do percurso, 
e neste processo de "compartimentação" , apenas segmentamos os percursos , e 
os percorremos em outra ordem, sem alterar o comprimento total.


Assim fica claro que qualquer política sempre pode ser reorganizada, sem 
ganhos ou perdas, de modo a levarmos inicialmente toda a água do ponto 
inicial INI para a primeira base , e então , toda a água desta base para a 
próxima , e assim sucessivamente , até alcançarmos o último ponto.

O inverso da segmentação também é válido : se entre A e P existem (2N+1) 
percursos (idas+voltas) , e se entre P e B também existem (2N+1) percursos , 
então P pode ser eliminado , e o transporte pode ser feito com (2N+1) 
percursos "compostos" , diretamente entre A e B .
Para verificarmos essa afirmação, chamemos de "a" e "b" as distâncias entre 
"A" e "P" , e entre "P" e "B" , respectivamente . Temos então que, no máximo 
, a água que haveria em  P seria "100*N - (2N+1)*a"  , de modo que em B 
poderia haver  "100*N - (2N+1)*a - (2N+1)*b" , que é o mesmo que "100*N - 
(2N+1)(a+b)" .


### Política ótima ###

Observe-se que para se fazer o transporte de determinada quantidade de água 
entre 2 bases consecutivas, a política ótima é "sair com 100 litros , e 
voltar com o mínimo suficiente para o percurso de volta, até a última ida, 
qdo então levaremos o resíduo que houver na base de partida" .

Entre outras coisas, vamos optar por eliminar pontos que segmentem 
desnecessariamente os percursos.

Observemos também que cada litro a mais no final do percurso , implica em 
uma quantidade maior na base anterior, e assim sucessivamente . Portanto , 
vamos resolver o problema vindo do final para o início, otimizando o gasto 
com a água .
Isso exige , por exemplo , que façamos o no. mínimo de viagens entre cada 
trecho, além de exigir que "enchamos o tanque" ao máximo em cada partida 
(100 l ou o resíduo que houver ).

Bem, para chegarmos ao final com 1000 l , precisamos de no mínimo 11 viagens 
de ida , a partir de algum ponto anterior aos 1000km . Para otimizar o custo 
dessas viagens (que se reflete exponencialmente no início) , devemos fazer 
as partidas com "o tanque cheio" , isto é , com 100 litros de cada vez . 
Isso garante que o custo das viagens seja o menor possível, além de 
"empurrar ao máximo" para o início a localização dessa base.

Portanto , a última base terá 1100 litros ,  e estará a 100/21 km do final 
(total de 21 viagens) .
Para colocarmos 1100 litros na última base , precisaremos de 12 viagens de 
ida a partir da penúltima base . Portanto , a penúltima base estará recuada 
de mais 100/23 km , e terá 1200 litros . E assim , sucessivamente .

Explicando de outra forma:
O "desperdício de água" (custo do transporte de água) entre 2 pontos é igual 
ao comprimento total dos segmentos que ligam esses 2 pontos.
Portanto, devemos minimizar a quantidade de segmentos , e maximizar o seu 
comprimento em cada trecho (vindo de trás p/ frente), visto que no próximo 
trecho mais segmentos serão necessários .
Assim, se no último ponto queremos ter 1000 L , devemos colocar 1100 L a 
100/21 km de distância do final. Para isso, precisamos de 1200 L a 100/23 km 
deste último ponto, e assim sucessivamente , até chegarmos a "quase" o 
início.
Apenas no último trecho (lá no início) é que faremos , das 2N+1 viagens , N 
partidas com 100L , e a última somente com o necessário para totalizarmos os 
100*N litros da primeira base.

Assim , listando os depósitos de água , e seus posicionamentos (do final 
para o início) até a primeira base , temos o seguinte:
------------------------------
1000 L - ponto final (FIM)
1100 L - 100/21 km para o final
1200 L - 100/23 km para a próxima base
.
.
.
N*100 L - 100/(2*N-1) km para a próxima base <- PRIMEIRA BASE

??? L - ponto inicial (INI) , ??? km para a primeira base
------------------------------

A distância da primeira base ao ponto final será :

S = 100/21 + 100/23 + ... + 100/(2N-1) , N o maior possível , que ainda 
permita "S < 1000"

A distância entre o início e a primeira base é "1000 -S" , e o gasto 
("desperdício") nesse primeiro trecho será (1000-S)*(2N+1) , de forma que o 
gasto total será :


[1000 - ( 100/21 + 100/23 +...+ 100/(2N-1) ) ] * (2N+1) + 100N  Litros


[]´s
Rogério.

_________________________________________________________________
MSN Hotmail, o maior webmail do Brasil.  http://www.hotmail.com

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