## 10487 - Closest Sums

Moderator: Board moderators

Antonio Ocampo
Experienced poster

Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Well, Antonio,

I think that your min is initialized to too small a value. Maybe the query number is really high and so the difference between sums and the query is large.
I'm always willing to help, if you do the same.
Ryan Pai
Learning poster

Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA

Thx for your help Ryan Pai. At last, I got AC

Keep posting
Antonio Ocampo
Experienced poster

Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

### 10487 WA- I don't know why.

This is my code:

#include <stdio.h>

long t,akt;
long tab[1001];
int n,m,c,i;

void licz(long co);
void sortowanie(int p, int k);
void uprosc();

int main()
{
c=0;
while (1==1)
{
scanf("%d",&n);
if (n==0)
return 0;
c++;
for (i=1;i<=n;i++)
scanf("%d",&tab[i]);
sortowanie(1,n);
uprosc();
scanf("%d",&m);
printf("Case %d:\n",c);
for (i=1;i<=m;i++)
{
scanf("%d",&t);
printf("Closest sum to %d is ",t);
if (n>1)
licz(t);
else
printf("0.\n");
}
}
return 0;
}

long abs(long co)
{
if (co<0)
co=-co;
return co;
}

long szukaj(long co)
{
long p=1,k=n-1,poz;
long best;
poz=1;
if (poz==akt)
poz++;
if (co<=tab[poz])
return tab[poz];
poz=n;
if (poz==akt)
poz--;
if (co>=tab[poz])
return tab[poz];
while (1==1)
{
poz=(p+k)/2;
if ((tab[poz]<=co) && (tab[poz+1]>=co))
break;
if (co<tab[poz])
k=poz-1;
else
p=poz+1;
}
if (tab[poz]==akt)
{
best=tab[poz+1];
if (poz>2)
{
if ((co-abs(tab[poz-1]))<(co-best))
best=tab[poz-1];
}
return best;
}
if (tab[poz+1]==akt)
{
best=tab[poz];
if (poz<n)
{
if ((co-abs(tab[poz+1]))<(co-best))
best=tab[poz+1];
}
return best;
}
if (abs(co-tab[poz])<=abs(co-tab[poz+1]))
return tab[poz];
else
return tab[poz+1];
}

void licz(long co)
{
long suma,t;
akt=1;
suma=szukaj(co-tab[1])-co+tab[1];
for (int i=2;i<=n;i++)
{
akt=i;
t=szukaj(co-tab[i])-co+tab[i];
if (abs(t)<abs(suma))
suma=t;
if (suma==0)
break;
}
printf("%d.\n",co+suma);
}

void zamiana(int a, int b)
{
long t;
t=tab[a];
tab[a]=tab[b];
tab[b]=t;
}

void sortowanie(int p,int k)
{
if (p<k)
{
int m=p;
for (int i=p+1;i<=k;i++)
if (tab[i]<tab[p])
zamiana(i,++m);
zamiana(p,m);
sortowanie(p,m-1);
sortowanie(m+1,k);
}
}

void uprosc()
{
int k=1;
for (int i=2;i<=n;i++)
if (tab[i]!=tab[k])
{
k++;
zamiana(i,k);
}
n=k;
}

NOthing special
qndel
New poster

Posts: 13
Joined: Tue Feb 03, 2004 11:00 am
Location: Opole

### 10487 WA

Hrrrmmm. Why am I getting WA? I've read all the other posts for this problem.. nothing helps

Code: Select all
`code removed after AC :)`

Thanks!
- Andrew
drewsome
New poster

Posts: 16
Joined: Mon Dec 01, 2003 1:20 am

Yeah, I got AC Here is another testcase to help anyone who might have WA:

4
1
4
7
8
3
0
5
100000

Case 1:
Closest sum to 0 is 5.
Closest sum to 5 is 5.
Closest sum to 100000 is 15.

- Andrew
drewsome
New poster

Posts: 16
Joined: Mon Dec 01, 2003 1:20 am

### 10487 how to use binary search

1. input data
2. sort them(qsort)
3. binary search

but how do I use binary search to find the closest sum
Could somebody give me some example or pusedo code
Cause I don't want to code my program so messly
Give me direction and pusedo code

lonelyone
Learning poster

Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

There can be at most 1000 numbers. So, number of (sum of 2 distinct terms) is less than (1000*1000/2+1).

First store all the possible sums. Then you can use linear search.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

### I still got WA :'(

I passed all tests posted on the board, but it's still WA :'( (also switched from bin-search to linear), please help me
Code: Select all
`Aced`
Last edited by FAQ on Fri Mar 24, 2006 12:38 pm, edited 1 time in total.
FAQ
Learning poster

Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

I think your code is not right. Try the following i/o set...

Input:
Code: Select all
`513710126345610120`

Output:
Code: Select all
`Case 1:Closest sum to 3 is 4.Closest sum to 4 is 4.Closest sum to 5 is 4.Closest sum to 6 is 4.Closest sum to 10 is 10.Closest sum to 12 is 11.`

Hope it helps.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

### WA :'(

Fixed, and still WA
Code: Select all
`ACed`
Last edited by FAQ on Fri Mar 24, 2006 12:36 pm, edited 1 time in total.
FAQ
Learning poster

Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Still some errors. Try the following i/o set...

Input:
Code: Select all
`33551100`

Output:
Code: Select all
`Case 1:Closest sum to 10 is 8.`

And the spelling is 'Closest', not 'Closet'.

Hope it helps.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

oh God, you're right, wrong spelling, only that silly mistake >_<
Thanks a lot Jan
FAQ
Learning poster

Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

### Why WA ???

Code: Select all
`ACed...`
jan_holmes
Experienced poster

Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore

### 10487 - WA WA WA - need test cases

After 14 submissions and 14 consecutive failure... i am so tired...
Can you tell me what is wrong here ?
Or can anyone give me some effective testcases ...

p-l-e-a-s-e ?

Code: Select all
`/* * 10487 closest sum * submission 1 RE 2 RE 3 RE 4 RE 5 WA * coded at 8:09am, april 13, 2006 * */#include <stdio.h>#include <stdlib.h>long long sum[1000000];long long myabs(long long x) {    return (x>0) ? x : (-1*x);}int comp(const void *a, const void *b) {    long long *x=(long long *)a;    long long *y=(long long *)b;    if(*x>*y) return 1;    if(*x<*y) return -1;    else return 0;}long long search(long long num,long long range) {    long long i;    long long min=100000000;    long long ans;    for(i=0;i<=range;i++) {        if(myabs(num-sum[i])<min) {            min=myabs(num - sum[i]);            ans=sum[i];        }else if(myabs(num-sum[i])>min ) break;    }return ans;}    int main() {    long long input[1005];    long long n,m;    long long i,j,k;    long long query;    long long cases=0;        while(scanf("%d",&n)==1) {        if(n==0) break;        for(i=0;i<n;i++) {            scanf("%d",&input[i]);        }        k=-1;                for(i=0;i<n;i++) {            for(j=i+1;j<n;j++) {                if(input[i]==input[j]) continue;                sum[++k]= input[i] + input[j];            }        }        qsort(sum,k+1,sizeof(sum[0]),comp);                scanf("%d",&m);        printf("Case %d:\n",++cases);        for(i=0;i<m;i++) {            scanf("%d",&query);            printf("Closest sum to %d is %d.\n",query,search(query,k));        }    }return 0;}`

I tried every topic avialable at e-board, none could give me the soln.
fahim
#include <smile.h>

smilitude
Experienced poster

Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

PreviousNext