## 10487 - Closest Sums

Moderator: Board moderators

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:
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.

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
Thx for your help Ryan Pai. At last, I got AC

Keep posting

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

### 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);
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)-co+tab;
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;
tab=t;
}

void sortowanie(int p,int k)
{
if (p<k)
{
int m=p;
for (int i=p+1;i<=k;i++)
if (tab<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!=tab[k])
{
k++;
zamiana(i,k);
}
n=k;
}

NOthing special

drewsome
New poster
Posts: 16
Joined: Mon Dec 01, 2003 1:20 am
Contact:

### 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
Contact:
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

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

### 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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 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.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
I think your code is not right. Try the following i/o set...

Input:

Code: Select all

``````5
1
3
7
10
12
6
3
4
5
6
10
12
0``````
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

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 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.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Still some errors. Try the following i/o set...

Input:

Code: Select all

``````3
3
5
5
1
10
0``````
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

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm
oh God, you're right, wrong spelling, only that silly mistake >_<
Thanks a lot Jan

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

### Why WA ???

Code: Select all

``````ACed...
``````

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

### 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>