U E D R , A S I H C RSS

Pairsumonious_Numbers/김태진

Pairsumonious_Numbers


#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

int arr[50],a[10],n;
int comp(int a,int b)
{
	return a<b;
}
int findThird(int Aindex,int i3)
{
	int x,i,j,flag=0,k;
	if(Aindex==n)return 1;
	for(i=2;i<n*(n-1)/2-1;i++){
		for(j=i+1;j<n*(n-1)/2;j++){
			if(abs(arr[i]-arr[j])==abs(a[Aindex-2]-a[Aindex-1])){
				x=abs(arr[i]-a[Aindex-2]);
				flag=1;
				for(k=0;k<Aindex;k++){
					if(a[k]==x)flag=0;
				}
				if(flag==1)break;
			}
			if(flag==1)break;
		}
	}
	a[Aindex]=x;
	findThird(Aindex+1,1);
	return 0;
}

int findFirstThree(int i1,int i2,int i3)
{
	int i,tmp;
	a[0]=(i1+i2-i3)/2;
	a[1]=(i2+i3-i1)/2;
	a[2]=(i1+i3-i2)/2;
	if(a[1]>a[2]){
		tmp=a[1];
		a[1]=a[2];
		a[2]=tmp;
	}
	findThird(3,1);
	return 0;
}

int isValid()
{
	int i,j,k=0;
	int checkArr[50];
	for(i=0;i<n-1;i++){
		for(j=i+1;j<n;j++){
			checkArr[k++]=a[i]+a[j];
		}
	}
	sort(checkArr,checkArr+n*(n-1)/2,comp);
	sort(arr,arr+n*(n-1)/2,comp);
	for(i=0;i<n*(n-1)/2;i++){
		if(checkArr[i]!=arr[i]){
			return -1;
		}
	}
	return 1;
}


int main()
{
	int i,j,k;

	
	while(1){
		if(feof(stdin))break;
		
		scanf("%d",&n);
		for(i=0;i<n*(n-1)/2;i++){
			scanf("%d",&arr[i]);
		}
		sort(arr,arr+n*(n-1)/2,comp);
		for(i=2;i<n;i++){
			findFirstThree(arr[0], arr[1], arr[i]);
			if(isValid()==1){
				sort(a,a+n,comp);
				for(j=0;j<n;j++){
					printf("%d ",a[j]);
				}
				return 0;
			}
		}
	}
				printf("Impossible");	
    return 0;
}


  • 예제 케이스에 두가지경우 빼곤 다 되네요. 두 경우는 무한루프 =ㅅ= -김태진
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:59
Processing time 0.0079 sec