Re: [obm-l] OBM 2003- Alguem fez esse?

["Rogerio Ponce" <rogerio_ponce@xxxxxxxxxxx>]

Olá Domingos,
sua solução está perfeita!
Eu havia imaginado uma solução um pouquinho diferente:

Se houver apenas um meio de transporte para as N cidades, a inserção de X 
pode ocorrer em qualquer lugar, e a solução é trivial.

Com 2 meios de transporte, suponhamos A B C cidades consecutivas, com a 
transição em B. Sem perda de generalidade, AB pode ser considerada ferrovia, 
e BC pode ser rodovia.
Se XB for ferrovia, faca a inclusão de X entre B e C, obtendo o circuito A B 
X C.
Se XB for rodovia, faca a inclusão de X entre A e B, obtendo o circuito A X 
B C.

Abraços,
Rogério.



>>Olá pessoal, esqueceram de fazer este problema...
>>
>>
>>Há N cidades em Tumbólia. Cada duas cidades desse país são
>>ligadas por uma rodovia ou uma ferrovia, não existindo nenhum
>>par de cidades ligadas por ambos os meios.
>>
>>Um turista deseja viajar por toda a Tumbólia, visitando cada cidade
>>exatamente uma vez, e retornar a cidade onde ele começou sua jornada.
>>
>>Prove que é possível escolher a ordem na qual as cidades serão visitadas
>>de modo que o turista mude o meio de transporte no máximo uma vez.
>
>Esse é um problema de grafos.
>Veja que para N = 2 o problema é trivial.
>Vamos mostrar que para N + 1 também conseguimos resolver o problema.
>Agora Tumbólia tem N + 1 cidades e já montamos um circuito (um itinerário 
>onde visitamos cada cidade uma única vez) de tamanho N onde trocamos de 
>transporte no máximo 1 vez. Suponha que X seja a cidade que ficou de fora 
>deste circuito.
>
>Se o circuito formado só possui um meio de transporte, podemos adicionar X 
>ao circuito e trocar de meio de transporte no máximo 1 vez (faça um 
>desenho...).
>
>Se o circuito formado já troca de transporte ao passar pela cidade Y 
>teremos cuidados extras. Podemos assumir (sem perda de generalidade) que o 
>circuito de N cidades começa em Y e chega até Z através de rodovia e de Z 
>até Y utiliza ferrovia.
>
>Se X se liga a Y através de ferrovia, insira X logo após Y no circuito e 
>veja que isso dá uma solução.
>Analogamente, se X se liga a Z através de ferrovia, então coloque X 
>imediatamente antes de Z no circuito.
>
>Sobrou apenas o caso em que X se liga a Y e Z através de rodovias.
>Neste caso forme um circuito começando Z, passando por X, depois Y, depois 
>siga o circuito original a partir de Y até encontrar o predecessor de Z, Z' 
>(no circuito original), vá de Z' até o antecessor de Y, Y' (também no 
>circuito original) e depois siga até Z pela direção contrária ao circuito 
>original.
>
>Por texto fica confuso, mas se você desenhar, vai ver que essa construção 
>funciona.
>
>[ ]'s

_________________________________________________________________
MSN Messenger: converse com os seus amigos online.  
http://messenger.msn.com.br

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