10400 - Game Show Math

10400 - Game Show Math.cpp

/**
 * Tittle:	10400 - Game Show Math
 * Author:	Cheng-Shih, Wong
 * Date:	2015/08/13
 */

// include files
#include <bits/stdc++.h>

using namespace std;

// definitions
#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
#define clr(x,v) memset( x, v, sizeof(x) )
#define F first
#define S second
#define PB push_back
#define INF 32000
#define N 105

// declarations
int t;
int n, target;
bool vis[N][2*INF+5];
vector<int> num;
vector<char> op;

// functions
void output()
{
	cout << num[0];

	FOR( i, 1, op.size() )
		printf( "%c%d", op[i-1], num[i] );
	
	printf( "=%d\n", target );
}

bool dfs( int idx, int res )
{
	if( !vis[idx][INF+res] ) vis[idx][INF+res] = true;
	else return false;

	if( idx == n ) {
		return res == target;
	}

	// +
	if( res+num[idx] <= INF ) {
		op.PB( '+' );

		if( dfs(idx+1, res+num[idx]) )
			return true;

		op.pop_back();
	}

	// -
	if( res-num[idx] >= -INF ) {
		op.PB( '-' );

		if( dfs(idx+1, res-num[idx]) )
			return true;

		op.pop_back();
	}

	// *
	if( -INF <= res*num[idx] && res*num[idx] <= INF ) {
		op.PB( '*' );

		if( dfs(idx+1, res*num[idx]) )
			return true;

		op.pop_back();
	}

	// /
	if( res%num[idx] == 0 ) {
		op.PB( '/' );

		if( dfs(idx+1, res/num[idx]) )
			return true;

		op.pop_back();
	}

	return false;
}

// main function
int main( void )
{
	int v;
	bool valid;

	// input
	cin >> t;

	while( t-- ) {
		cin >> n;
		num.clear();
		
		FOR( i, 1, n ) {
			cin >> v;
			num.PB( v );
		}	

		cin >> target;
		op.clear();

		clr( vis, false );
		valid = dfs( 1, num[0] );

		// output
		if( !valid ) puts("NO EXPRESSION");
		else output();
	}
	
	return 0;
}