2014
03-07

# The first place of 2^n

LMY and YY are mathematics and number theory lovers. They like to find and solve interesting mathematic problems together. One day LMY calculates 2n one by one, n=0, 1, 2,… and writes the results on a sheet of paper: 1，2，4，8，16，32，64，128，256，512，1024，……

LMY discovers that for every consecutive 3 or 4 results, there must be one among them whose first digit is 1, and comes to the conclusion that the first digit of 2n isn’t evenly distributed between 1 and 9, and the number of 1s exceeds those of others. YY now intends to use statistics to prove LMY’s discovery.

Input consists of one or more lines, each line describing one test case: an integer N, where 0≤N≤10000.

End of input is indicated by a line consisting of -1.

Input consists of one or more lines, each line describing one test case: an integer N, where 0≤N≤10000.

End of input is indicated by a line consisting of -1.

0
1
3
10
-1

1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0
1 1 0 1 0 0 0 1 0
4 2 1 1 1 1 0 1 0

#include <stdio.h>
#include <math.h>
const double eps=1.0e-6;
int dp[10010][10];
void Init( )
{
int y;
double s=log10(2), t, x;
dp[0][1]=1;
for( int i=1; i<=10000; ++ i ){
for( int j=1; j<10; ++ j ){
dp[i][j]=dp[i-1][j];
}
t=s*i;
x=t-(int)t;
y=( int )(pow( 10, x )+eps);// 注意有精度损失
dp[i][y]++;
}
}
int main( )
{
Init( );
int N;
while( ~scanf( "%d", &N ) ){
if( N==-1 )break;
for( int i=1; i<10; ++i ){
printf( i==9?"%d\n":"%d ", dp[N][i] );
}
}
return 0;
}