## 10202 - Pairsumonious Numbers

Moderator: Board moderators

### 10202 - Pairsumonious Numbers

i've checked my program, but wa, why?
would you help me? thanks!
[c]
//pairsumonious numbers
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>

int result[9];
int data[37];
int count;
unsigned char used[37];

int SortFunction(const void *a,const void *b)
{
return *(int*)a-*(int*)b;
}

int Check(int first)
{
int i,j,k,cur,t;
result[0]=first;
cur=1;
memset(used+1,0,count);
for (i=1;i<=count;i++)
{
if (!used[i])
{
result[cur]=data[i]-first;
used[i]=1;
for (j=1;j<cur;j++)
{
t=result[j]+result[cur];
for (k=i+1;(k<=count && data[k]<=t);k++)
{
if (data[k]==t && !used[k])
{
used[k]=1;
break;
}
}
if (k>count || data[k]>t)
return 0;
}
cur++;
}
}
return 1;
}

void main()
{
int i,p;
char line[400];
while (gets(line))
{
i=0;
while (sscanf(line,"%d %[^\0]",&data[i++],line)==2);
if (i<4)
continue;
count=i-1; //equals data[0]*(data[0]-1)/2
qsort((void*)(data+1),count,sizeof(int),SortFunction);
for (i=3;i<=count;i++)
{
p=data[1]+data[2]-data[i];
if (p&1) //odd number
continue;
if (Check(p/2) && result[1]>=result[0]) //result[1]>=result[0] is needed?
break;
}
if (i>count)
printf("Impossible\n");
else
{
printf("%d",result[0]);
for (i=1;i<data[0];i++)
printf(" %d",result[i]);
printf("\n");
}
}
}
[/c]
none
newhh2002
New poster

Posts: 11
Joined: Sun Jan 26, 2003 4:25 pm

### 10202 -- Pairsumonious Numbers

hi all, I have a question.
Could this problem solve with DP?

I have tried to solve this with DFS, finding out all possibility.
but it seems that my method waste a lot of time.
I ponder if a more efficient way exists, just like DP.

Anyone have an idea about solve Q10202 with DP?

----
DJWS, a newbie in programming
DJWS
Learning poster

Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan

Larry
Guru

Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City

Thanks for the info, Larry
I will give a try with this method.

----
DJWS, a newbie in programming
DJWS
Learning poster

Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan

### 10202...Pairsumonious Numbers

can anyone tell me what will be the approach for this problem??
i couldnt model this problem for coding. Is it a backtraking problem or mathematical?
Give some hints.

thnx
DP
Learning poster

Posts: 62
Joined: Sun Aug 13, 2006 9:15 am

I use backtracking approach, but I think there is a good solution for this problem without backtracking. I guess this from the ranklist!
Moha
Experienced poster

Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran

But it could be helpfull if you give some hints.

thnx
DP
Learning poster

Posts: 62
Joined: Sun Aug 13, 2006 9:15 am

A hint in backtracking approach? you can always assume that the first number is 0 and the last one is the largest one.

So we need to find out the others. a simple backtraking method is select the numbers from the given numbers and check all of pairs if they make a solution.

A hint for another solution is: the smallest number is always the second one!
Moha
Experienced poster

Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran

thnx Moha.
DP
Learning poster

Posts: 62
Joined: Sun Aug 13, 2006 9:15 am

### Re: 10202 - Pairsumonious Numbers

Oh my god this problem becomes so easy to implement if you read the solution here:
http://www.topcoder.com/tc?module=Stati ... &d2=srm182
stcheung
Experienced poster

Posts: 114
Joined: Mon Nov 18, 2002 6:48 am

### Re: 10202 - Pairsumonious Numbers

The TopCoder links are broken. Could someone point or explain a better solution than exhaustive search?

Perhaps solving the implicit linear equations system?