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