10487 - Closest Sums

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

Moderator: Board moderators

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

Post by Antonio Ocampo » Mon Feb 28, 2005 1:08 am

Please help me!!!!!!!!!!!!!!!! :cry:

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

Post by Ryan Pai » Wed Mar 02, 2005 1:30 am

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

Post by Antonio Ocampo » Wed Mar 02, 2005 4:43 am

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

Keep posting :wink:

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

10487 WA- I don't know why.

Post by qndel » Tue Jun 07, 2005 10:52 am

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]
NOthing special

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

10487 WA

Post by drewsome » Wed Aug 10, 2005 10:01 am

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:

Post by drewsome » Wed Aug 10, 2005 6:33 pm

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

Post by lonelyone » Wed Oct 05, 2005 8:16 pm

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

Post by Jan » Fri Dec 30, 2005 11:29 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

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

I still got WA :'(

Post by FAQ » Thu Mar 23, 2006 4:52 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Mar 23, 2006 8:07 pm

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 :'(

Post by FAQ » Fri Mar 24, 2006 2:59 am

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Mar 24, 2006 10:37 am

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'. :D

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

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

Post by FAQ » Fri Mar 24, 2006 12:39 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 ???

Post by jan_holmes » Sun Apr 09, 2006 2:28 am

Code: Select all

ACed...

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

10487 - WA WA WA - need test cases

Post by smilitude » Thu Apr 13, 2006 5:16 am

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>

Post Reply

Return to “Volume 104 (10400-10499)”