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: [EMAIL PROTECTED]
>>Reply-To: [EMAIL PROTECTED]
>>To: [EMAIL PROTECTED]
>>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" <[EMAIL PROTECTED]>
>> >>Reply-To: [EMAIL PROTECTED]
>> >>To: [EMAIL PROTECTED]
>> >>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 � <[EMAIL PROTECTED]>
>> >>=========================================================================
>> >
>> >
>> >
>> >
>> >_________________________________________________________________
>> >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 � <[EMAIL PROTECTED]>
>> >=========================================================================
>> >
>>
>>
>>
>>------------------------------------------
>>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 � <[EMAIL PROTECTED]>
>>=========================================================================
>
>
>
>
>_________________________________________________________________
>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 � <[EMAIL PROTECTED]>
>=========================================================================
>
------------------------------------------
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 � <[EMAIL PROTECTED]>
=========================================================================
