[UVa] 10344 - 23 out of 5

題意:
(from luckycat)


解法:
DFS枚舉所有可能。

注意:

程式碼:

	/**
	* Tittle: 10344 - 23 out of 5
	* Author: Cheng-Shih, Wong
	* Date: 2015/07/04
	*/
	// 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) )
	typedef vector<int> VI;
	// declarations
	int num[5];
	VI seq;
	bool vis[5];
	// functions
	bool input( void )
	{
	FOR( i, 0, 4 ) scanf( "%d", &num[i] );
	FOR( i, 0, 4 )
	if( num[i] != 0 ) return true;
	return false;
	}
	bool check( int l, int res )
	{
	if( l == 5 ) {
	return res==23;
	}
	if( check(l+1,res+seq[l]) ) return true;
	if( check(l+1,res-seq[l]) ) return true;
	if( check(l+1,res*seq[l]) ) return true;
	return false;
	}
	bool mkSeq( int l )
	{
	if( l == 5 ) {
	return check( 1, seq[0] );
	}
	FOR( i, 0, 4 ) if( !vis[i] ) {
	vis[i] = true;
	seq.push_back( num[i] );
	if( mkSeq(l+1) ) return true;
	seq.pop_back();
	vis[i] = false;
	}
	return false;
	}
	void solve( void )
	{
	clr( vis, false );
	seq.clear();
	puts( mkSeq(0) ? "Possible":"Impossible" );
	}
	// main function
	int main( void )
	{
	// input
	while( input() ) {
	solve();
	}
	return 0;
	}

view raw 10344 - 23 out of 5.cpp hosted with ❤ by GitHub