3208.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3208  User Id:fzk 
Memory:24K  Time:0MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>

int s[14][4];

int to[4][10];

void doit( ) {
	int i, j, k;
	
	for( i=0; i<3; i++ )
	for( j=0; j<10; j++ )
		to[i][j] = 0;
	to[0][6] = 1;
	to[1][6] = 2;
	to[2][6] = 3;
	for( j=0; j<10; j++ )
		to[3][j] = 3;

	s[0][3] = 1;

	for( i=1; i<14; i++ )
	for( j=0; j<4; j++ )
	for( k=0; k<10; k++ )
		s[i][j] += s[i-1][to[j][k]];
}

int main( ) {
	int i, j, n, k, t;
	__int64 ans;

	doit( );
	scanf( "%d", &t );

	while( t-- ){
		scanf( "%d", &n );
		ans = 0;
		k = 0;
		for( i=0; i<14 && s[i][0] < n; i++ )
			;
		while( i-- ) {
			for( j=0; j<10 && s[i][to[k][j]] < n; j++ )
				n -= s[i][to[k][j]];
			ans = ans*10+j;
			k = to[k][j];
		}
		printf( "%I64d\n", ans );
	}
	return 0;
}