[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[obm-l] Re: [obm-l] Re: [obm-l] mais uma!
Oi David,
Desculpe-me, um erro de conta me levou ao contra-exemplo e a
conclusão errados. De fato, pensando no problema agora ao invés de só fazer
conta, percebi que a a melhor solução tem realmente o número de passos que
você mencionou.
De fato, em qualquer passo, o número de amebas presentes é da forma (1
+ 6k - n) em que n é o número de vezes em que morreu uma ameba e k <= (1
+ 7 + 7^2.. + 7^N), em que N é o número de de vezes que nós usamos para
"multiplicarmos" amebas.
Bom, a melhor solução é com k=334 e n=5. Para k=334 temos que N mínimo
é 4, logo t(tempo mínimo)= n + N = 5 + 4= 9, o que você já havia concluído
há bastante tempo.
Camilo
-- Mensagem original --
>É, pode ser que eu esteja interpretando errado o problema, ou minha solução
>
>é furada. Mas como vc faz p/ ir do 343 p/ 2002 em 1 segundo?
>Em um segundo, só consigo ir do 343 p/ 2005 (7*277+(343-277)), ou p/ 1999
>
>(7*276+(343-276)).
>Segundo a minha interpretação, se em um estágio temos a amebas, no próximo
>
>temos uma das seguintes possibilidades:
>a-1, 7a, 7(a-1)+1, 7(a-2)+2, ..., 7+(a-1), a (são a+2 possibilidades no
>total).
>P/ vc tb?
>
>>From: camilojr@zipmail.com.br
>>Reply-To: obm-l@mat.puc-rio.br
>>To: obm-l@mat.puc-rio.br
>>Subject: [obm-l] Re: [obm-l] mais uma!
>>Date: Sat, 3 Aug 2002 02:02:52 -0300
>>
>> Não entendi muito bem essa idéia de que a mudança de regras não altere
>>o tempo mínimo. Se eu compreendi corretamente o problema original, existem
>>várias soluções que conduzem a um tempo mínimo de 6 segundos. Uma delas
>>é:
>>
>> 7 - 49 - 343 - 2002 - 2001 - 2000
>>
>> um abraço,
>> Camilo
>>
>>-- Mensagem original --
>>
>> >Primeiro note que podemos alterar levemente as regras, de modo que elas
>>nos
>> >
>> >convenham e o tempo mínimo não se altere. Em vez de "algumas das amebas
>>
>> >dividem-se em sete novas amebas", podemos impor "todas as amebas
>>dividem-se
>> >
>> >em sete novas amebas". É melhor ver isso com um exemplo (eu comecei
a
>> >escrever mas tava ficando grande e chato):
>> >Para ir de 6 amebas para 25 amebas o mais rápido possível, vc pode tanto
>> >
>> >fazer:
>> >6 -> 5 -> 4 -> 28 -> 27 -> 26 -> 25, como
>> >6 -> 30 -> 29 -> 28 -> 27 -> 26 -> 25, e ambas são feitas no menor tempo
>> >
>> >possível. (Não provei, mas acho que dá p/ entender o que eu tô fazendo,
>>
>> >tendo pensado um pouquinho no problema. Caso contrário, diga.)
>> >
>> >Agora o problema. A resposta é 9 segundos:
>> >Primeiro veja que dá p/ fazer nesse tempo: 1 -> 7 -> 6 -> 42 -> 41 ->
>287
>> >->
>> >286 -> 2002 -> 2001 -> 2000.
>> >Agora tente fazer em menos (digamos em t<9 segundos). De trás p/ frente:
>> >
>> >como 2000 não é divisível por 7, em t-1 teríamos que ter 2001 amebas
>>(aqui
>> >
>> >foi útil aquela mudança nas regras). Como 2001 não é divísivel por 7,
>em
>> >t-2
>> >teríamos que ter 2002. Em t-3, temos ou 2003 ou 2002/7=286. Mas se fosse
>> >
>> >2003, seguindo esse raciocínio teríamos em t-8 2008, mas t-8<9-8=1,
isto
>> >é,
>> >t-8 é o tempo 0, contradição. Então em t-3 temos 286, e em t-4, 287.
Em
>>t-5
>> >
>> >temos que ter 287/7=41, pois senão temos 288, e vai demorar mais 6 passos
>> >
>> >até chegarmos num múltiplo de 7, estourando os 9 segundos. Etc.
>> >
>> >David
>> >
>> >>From: "Adherbal Rocha Filho" <adherbalmat@hotmail.com>
>> >>Reply-To: obm-l@mat.puc-rio.br
>> >>To: obm-l@mat.puc-rio.br
>> >>Subject: [obm-l] mais uma!
>> >>Date: Fri, 02 Aug 2002 21:36:27 +0000
>> >>
>> >>
>> >>
>> >>
>> >>ae pessoal, mais uma questão pra qm quiser tentar:
>> >>1.Em um tubo de ensaio há exatamente 1 ameba.A cada segundo algumas
das
>> >
>> >>amebas devidem-se em sete novas amebas ou morre exatamente uma das
>> >>amebas.Determine o período mínimo de tempo após o qual o nº de amebas
>>no
>> >
>> >>tubo de ensaio será igual a 2000.
>> >>
>> >>Blz!
>> >>Adherbal
>> >>
>> >>_________________________________________________________________
>> >>MSN Photos é a maneira mais fácil e prática de editar e compartilhar
>sua
>> >
>> >>fotos: http://photos.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
>> >>O administrador desta lista é <nicolau@mat.puc-rio.br>
>> >>=========================================================================
>> >
>> >
>> >
>> >
>> >_________________________________________________________________
>> >MSN Photos é a maneira mais fácil e prática de editar e compartilhar
sua
>> >
>> >fotos: http://photos.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
>> >O administrador desta lista é <nicolau@mat.puc-rio.br>
>> >=========================================================================
>> >
>>
>>
>>
>>------------------------------------------
>>Use o melhor sistema de busca da Internet
>>Radar UOL - http://www.radaruol.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
>>O administrador desta lista é <nicolau@mat.puc-rio.br>
>>=========================================================================
>
>
>
>
>_________________________________________________________________
>Tenha você também um MSN Hotmail, o maior webmail do mundo:
>http://www.hotmail.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
>O administrador desta lista é <nicolau@mat.puc-rio.br>
>=========================================================================
>
------------------------------------------
Use o melhor sistema de busca da Internet
Radar UOL - http://www.radaruol.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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================