2011.txt

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

#include <stdio.h>
#include <math.h>
#include <algorithm>

int ans[20], an;
int temp[20];

int get( int num, int s, int &r ) {
	int g = 0, tg=1, tr=1;
	bool key = true;
	r = 0;
	while( num ) {
		if( s & 1 ) {
			key = num%10;
			g += num%10*tg;
			tg *= 10;
		}
		else {
			r += num%10*tr;
			tr *= 10;
		}
		num /= 10;
		s >>= 1;
	}
	if( !key )
		return -1;
	else
		return g;
}

void search( int s, int k ) {
	temp[k++] = s;

	int m, t=s, i, r;
	for( m=0; t; m++, t/=10 )
		;
	for( i=1; i<(1<<m)-1; i++ ) {
		t = get( s, i, r );
		if( t > 1 && s%t == 0 )
			search( r, k );
	}

	if( k > an || k == an && !std::lexicographical_compare( ans, ans+an, temp, temp+an ) ) {
		std::copy( temp, temp+k, ans );
		an = k;
	}
	return;
}

int main( ) {
	int n, i;
	while( scanf( "%d", &n ) == 1 && n ) {
		an = 0;
		search( n, 0 );
		for( i=0; i<an; i++ ) {
			if( i ) printf( " " );
			printf( "%d", ans[i] );
		}
		printf( "\n" );
	}
	return 0;
}