10202 - Pairsumonious Numbers

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
newhh2002
New poster
Posts: 11
Joined: Sun Jan 26, 2003 4:25 pm
Contact:

10202 - Pairsumonious Numbers

Post by newhh2002 »

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)
{
result[cur]=data-first;
used=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;
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);
printf("\n");
}
}
}
[/c]
none

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

10202 -- Pairsumonious Numbers

Post by DJWS »

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 :wink:

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

Post by Larry »


DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Post by DJWS »

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

----
DJWS, a newbie in programming :wink:

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

10202...Pairsumonious Numbers

Post by DP »

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

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha »

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

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

Post by DP »

hi moha thnx for your reply.
But it could be helpfull if you give some hints. :)

thnx

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha »

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!

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

Post by DP »

thnx Moha.

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Re: 10202 - Pairsumonious Numbers

Post by stcheung »

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

darkseed
New poster
Posts: 2
Joined: Tue Oct 19, 2010 1:14 am

Re: 10202 - Pairsumonious Numbers

Post by darkseed »

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

Perhaps solving the implicit linear equations system?

Thanks in advance.

Post Reply

Return to “Volume 102 (10200-10299)”