imported>jereneal20 at 16:52, 6 September 2012

2012-09-06T16:52:45Z

← Older revision	Revision as of 16:52, 6 September 2012
(No difference)

imported>jereneal20 at 16:52, 6 September 2012

2012-09-06T16:52:34Z

New page

== 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;
}

* 예제 케이스에 두가지경우 빼곤 다 되네요. 두 경우는 무한루프 =ㅅ= -[[김태진]]

Pairsumonious Numbers/김태진 - Revision history

imported>jereneal20 at 16:52, 6 September 2012

imported>jereneal20 at 16:52, 6 September 2012