Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

KOCH - Crescimento das populações de bacilos

Heinrich Hermann Robert Koch foi um médico alemão que viveu de 1843 a 1910 e ficou famoso por ter isolado o bacilo causador da tuberculose. Seus estudos sobre a doença que causava muitas mortes até meados do século XX possibilitaram o desenvolvimento de uma vacina que salvou milhões de vidas por todo o mundo. Robert Koch foi agraciado em 1905 com o prêmio Nobel de Medicina e é considerado um dos pais da Microbiologia.

Um dos estudos de Koch estava ligado com a velocidade de crescimento das populações de bacilos. Koch observou que os bacilos demoram um instante de tempo para atingir a maturidade e iniciar a divisão celular. A partir daí, o bacilo gera um novo indivíduo a cada instante de tempo por meio de uma divisão. Dessa forma, se partirmos de uma população inicial com apenas um indivíduo, no instante seguinte teremos ainda um (ele atinge a maturidade para divisão), no seguinte teremos 2, no outro 3, então 5 e assim por diante.

Sua tarefa é, dado um inteiro K, 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.

Entrada

A primeira linha de um caso de testes contém um inteiro T que indica o número de instâncias subseqüentes. Cada instância é composta por apenas uma linha que contém um inteiro K (1 ≤ K ≤ 10^1000000, ou seja, K pode ter 1000000 de dígitos).

Saída

Para cada instância imprima uma linha contendo os três últimos dígitos do número de bacilos após K instantes de tempo.

Exemplo de entrada
5
1
4
10
21312
1000000

Exemplo de saída
001
003
055
744
875


Adicionado por:Wanderley Guimarăes
Data:2008-10-01
Tempo limite:0.123s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO PERL6 PY_NBC SCALA TCL
Origem:Primeira Seletiva para Maratona de Programacao IME-USP - 2006

hide comments
2011-09-27 01:05:42 Rodrigo Roim Ferreira [ITA]
Haja criatividade nesses enunciados.

Last edit: 2012-02-19 04:04:46
2011-02-01 02:35:44 Maycon Maia Vitali [UFES]
Como k pode ser menor ou IGUAL ŕ 10^1000000, entăo k pode ser 10^1000000, que dariam 1000001 dígitos. :-)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.