1902.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1902 on 2005-10-31 at 15:10:07 */ 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
	int f[16], sum[64];
	bool used[64];
	int n, m, k, p, q;
	int i, j, l, r;
	bool sloved;
	
	while(scanf("%d", &n) == 1) {
		m = n * (n - 1) / 2;
		for(i = 0; i < m; i++) {
			scanf("%d", &sum[i]);
		}
		sort(sum, sum+m);
		sloved = false;
		k = sum[0] + sum[1];
		for(i = 2; i < m; i++) {
			if((k + sum[i]) % 2 == 0) {
				p = (k + sum[i]) / 2;
				f[0] = p - sum[i];
				f[1] = p - sum[1];
				f[2] = p - sum[0];
				memset(used, false, sizeof(used));
				used[0] = used[1] = used[i] = true;
				q = 3;
				sloved = true;
				for(j = 2; j < m && sloved; j++) {
					if(!used[j]) {
						f[q] = sum[j] - f[0];
						for(l = 0; l < q; l++) {
							for(r = j; r < m; r++) {
								if(!used[r] && sum[r] == f[l] + f[q]) {
									used[r] = true;
									break;
								}
							}
							if(r == m) {
								sloved = false;
								break;
							}
						}
						q++;
					}
				}
				if(sloved) {
					break;
				}
			}
		}
		if(sloved) {
			for(i = 0; i < n; i++) {
				if(i != 0) {
					putchar(' ');
				}
				printf("%d", f[i]);
			}
			putchar('\n');
		} else {
			printf("Impossible\n");
		}
	}
}