U E D R , A S I H C RSS

Pairsumonious_Numbers/권영기


#include<stdio.h>
#include<memory.h>
#include<algorithm>
#include<list>
#define M 100
#define N 12
using namespace std;
list <int> sum;
int ans[N], n, flag = 0, checkans[M], temp[M], cnt = 0;
int checker(){
	memset(checkans, 0, sizeof(int) * M);
	cnt = 0;
	for(int i = 1; i<=n; i++){
		for(int j = i+1; j<=n; j++){
			checkans[cnt++] = ans[i] + ans[j];
		}
	}
	sort(checkans, checkans+cnt);
	for(int i = 0; i<cnt; i++){
		if(checkans[i] != temp[i])return 0;
	}
	return 1;
}
void back(int s, list <int>::iterator iter){
	list <int>::iterator it1, it2, temp, tempit;
	int tempsum;
	if(s == n+1 && checker()){
		flag = 1;
		return;
	}

	for(it1 = iter; it1 != sum.end() && !flag; it1++){
		temp = it1;
		temp++;
		for(it2 = temp; it2 != sum.end()  && !flag; it2++){
			tempsum = (ans[s-1] + ans[s-2] + *it1 + *it2)/2;
			ans[s] = tempsum - ans[s-1] - ans[s-2];
			if(ans[s-2] <= ans[s-1] && ans[s-1] <= ans[s]){
				tempit = find(it2, sum.end(), ans[s-1] + ans[s]);
				//back(s+1, find(it2, sum.end(), ans[s-1] + ans[s]));
				back(s+1, tempit);
			}
		}
	}
}
int main(void)
{

	int m, i, tempsum, start = 1;
	while(scanf("%d", &n) == 1){
		if(start == 1){
			start = 0;
		}
		else if(start == 0){
			printf("\n");
		}
		flag = 0;
		memset(temp, 0, sizeof(int) * M);
		memset(ans, 0, sizeof(int) * N);
		while(!sum.empty())sum.pop_back();
		for(i = 0; i<n*(n-1)/2; i++){
			scanf("%d", &temp[i]);
		}
		m = i;
		sort(temp, temp + m);
		for(i = 2; i<m; i++){
			sum.push_back(temp[i]);
		}

		list<int>::iterator iter, tempit;
		for(iter = sum.begin(); iter!=sum.end(); iter++){
			tempsum = (temp[0] + temp[1] + *iter)/2;
			ans[1] = tempsum - *iter;
			ans[2] = tempsum - temp[1]; 
			ans[3] = tempsum - temp[0];
			if(ans[1] <= ans[2] && ans[2] <= ans[3]){
				tempit = find(sum.begin(), sum.end(), ans[2]+ans[3]);
				//back(4, find(sum.begin(), sum.end(), ans[2] + ans[3]));
				back(4, tempit);
				if(flag)break;
			}
		}
		if(!flag)printf("Impossible");
		else{
			for(i = 1; i<=n; i++){
				printf("%d", ans[i]);
				if(i != n)printf(" ");
			}
		}
		
	}


	return 0;
}



10546028 10202 Pairsumonious Numbers Accepted C++ 0.008 2012-08-31 07:07:56
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:59
Processing time 0.0089 sec