10487 - Closest Sums

[Antonio Ocampo]

Please help me!!!!!!!!!!!!!!!!

[Ryan Pai]

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.

[Antonio Ocampo]

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

Keep posting

[qndel]

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



if anybody see any mistakes please help me!!!!![/code]

[drewsome]

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]

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]

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

Thanks for your reply

[Jan]

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.

[FAQ]

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

[Jan]

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.

[FAQ]

Fixed, and still WA

Code: Select all

ACed

[Jan]

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.

[FAQ]

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

[jan_holmes]

Code: Select all

ACed...

[smilitude]

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.