Crescimento das populações de bacilos - Seletivas

Tarefa

Sua tarefa é, dado um inteiro K (1 <= K <= 10^1000000 ou seja, K pode ter 1000000 de dígitos), determinar os três últimos dígitos do número de bacilos após K instantes de tempo, partindo de uma população inicial com um indivíduo.

Como resolver:

Diante de uma rápida análise do problema KOCH, podemos perceber que se trata de manipulação de big numbers, quem nunca trabalhou com big numbers, aconselho baixar o The Art of Programming Contest (está ali na barra lateral), - um e-book com instruções, códigos genéricos e problemas de maratonas de programação em geral-, pois iremos precisar dele.

Para quem ainda não sacou a idéia, os números de bacilos após K instantes de tempo é simplesmente a sequência de fibonacci. Mas como conseguir o instante K da sequência de fibonacci, quando K pode ter 1000000 de dígitos? Precisaremos manipular big numbers. Para nos poupar tempo, já existe um algoritmo pronto para calcular qualquer instante da sequência de fibonacci, onde esse instante pode ser um número muito grande. (Ver página 219 - The Art of Programming Contest).

Com o código em mãos, nos resta pouco para resolver esse problema. Pesquisando no fórum do SPOJ, descobrimos que existe um padrão da resposta a cada 1500 instantes, então nos bastará apenas utilizar o resto da divisão de K por 1500, mas como fazer divisão de big numbers? Você descobrirá na página 215 no The Art of Programming Contest).

Agora que você já sabe como calcular qualquer big number instante da sequência de fibonacci e também sabe que o resto da divisão de K por 1500 é o número de bacilos, como iremos imprimir apenas os 3 últimos dígitos desse resto? Basta que você você divida novamente o resto por 1000. Independente do valor dessa divisão, para imprimir sempre 3 dígitos, mesmo que o valor dê menos que 3 dígitos, a formatação se dará dessa forma:

printf("%03ld",variavel); //03, quer dizer 3x o número zero

Veja no site do Vinícius Fortuna, os vários formatos de entrada e saída para competições em geral.

Problema: 3090. Crescimento das populações de bacilos

Dúvidas? Entre em contato ou deixe um comentário.