[UVa] 10202 - Pairsumonious Numbers

題目網址: http://goo.gl/S5ukPw

題意:
(from luckycat)


解法: 我們先假設 N 個數為 A1 <= A2 <= ... <= AN，當把 N*(N-1)/2 個兩兩和排序過後，最小的兩個必定是 A1+A2、A1+A3，但是接下來的都不能夠確定，所以開始枚舉 A2+A3，就可以分別求出 A1、A2、A3，這樣就可以往後推舉 A4、A5、...、AN 來確定枚舉的 A2+A3 是否成立。

TAG: Brute Forc

注意:

程式碼:

	/**
	* Tittle: 10202 - Pairsumonionous Numbers
	* Author: Cheng-Shih, Wong
	* Date: 2015/05/12
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <algorithm>
	#include <set>
	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 N 15
	typedef multiset<int> MTSI;
	// declarations
	int n, m;
	int sumofnum[N*N];
	MTSI sum, newsum;
	int num[N];
	bool findAns;
	// functions
	// main function
	int main( void )
	{
	int tmp;
	MTSI::iterator it;
	bool check;
	// input
	while( scanf( "%d", &n )==1 ) {
	m = n*(n-1)/2;
	FOR( i, 1, m ) {
	scanf( "%d", &sumofnum[i] );
	}
	sort( sumofnum+1, sumofnum+1+m );
	// solve
	sum.clear();
	findAns = false;
	sum = MTSI( sumofnum+3, sumofnum+m+1 );
	FOR( i, 3, m ) {
	tmp = sumofnum[1]+sumofnum[2]+sumofnum[i];
	if( tmp&1 ) continue;
	tmp /= 2;
	num[1] = tmp-sumofnum[i];
	num[2] = tmp-sumofnum[2];
	num[3] = tmp-sumofnum[1];
	findAns = true;
	newsum = sum;
	it = newsum.find( sumofnum[i] );
	newsum.erase( it );
	FOR( j, 4, n ) {
	it = newsum.begin();
	num[j] = (*it)-num[1];
	newsum.erase( it );
	check = true;
	FOR( k, 2, j-1 ) {
	it = newsum.find( num[j]+num[k] );
	if( it == newsum.end() ) {
	check = false;
	break;
	}
	newsum.erase( it );
	}
	if( !check ) {
	findAns = false;
	break;
	}
	}
	if( findAns )
	break;
	}
	// output
	if( findAns ) {
	printf( "%d", num[1] );
	FOR( i, 2, n ) printf( " %d", num[i] );
	putchar('\n');
	} else puts("Impossible");
	}
	return 0;
	}

view raw 10202 - Pairsumonious Numbers.cpp hosted with ❤ by GitHub