2844.txt

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

Source

Problem Id:2844  User Id:fzk 
Memory:52K  Time:841MS
Language:G++  Result:Accepted

Source 

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

using namespace std;

int a[1000], an = 0;
int res[1000];
int n, s, p, pv;
int counts;

int search( int k, int product, int sum, int step ) {
	int t;

	if( product == p && abs(s-sum)<=n-step && (n-step-abs(s-sum))%2 == 0 && ((sum>s?sum-s:0)+(n-step-abs(s-sum))/2)%2 == 0 )
		return step;
	if( abs(s-sum)>n-step && product*(abs(s-sum)-(n-step)) > pv )
		return 0;

	if( step >= n )
		return 0;

	while( k && a[k] > pv/abs(product) )
		k--;
	
	if( k < 0 )
		return 0;

	for( ; k>=0 ; k-- ) {
		if( pv%(a[k]*product) == 0 ) {
			res[step] = a[k];
			if( t = search( (k>an/2)?an/2:k, product*a[k], sum + a[k], step+1 ) )
				return t;
			res[step] = -a[k];
			if( t = search( (k>an/2)?an/2:k, product*(-a[k]), sum - a[k], step+1 ) )
				return t;
		}
	}

	return 0;
}

int main( ) {
	int i, t;

	scanf( "%d%d%d", &n, &s, &p );
	
	if( p == 0 ) {
		if( n == 1 ) {
			if( s == 0 )
				printf( "0\n" );
			else
				printf( "No solution\n" );
		}else {
			for( i=0; i<n-1; i++ )
				printf( "0 " );
			printf( "%d\n", s );
		}
		return 0; 
	}

	pv = abs( p );
	for( i=2; i*i<=pv; i++ ) {
		if( pv % i == 0 ) {
			a[an++] = i;
			if( i*i != pv ) a[an++] = pv/i;
		}
	}

	a[an++] = pv;
	a[an] = pv+1;
	sort( a, a+an );
	counts = 0;
	if( t = search( an-1, 1, 0, 0 ) ) {
		for( i=0; i<t; i++, n-- ) {
			if( i )printf( " " );
			printf( "%d", res[i] );
			s -= res[i];
		}
		for( i=0; i<fabs(s); i++, n-- )
			printf( " %d", s>0?1:-1 );
		for( i=0; i<n; i++ )
			printf( " %d", i&1?1:-1 );
		printf( "\n");
	}
	else
		printf( "No solution\n" );
		
	return 0;
}