## 10487 - Closest Sums

Moderator: Board moderators

Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:
Thanks for the tip on problem 10489, I got AC now!

But didn't undertand what you ment for problem 10487. Could you explain me a little bit further?

Thanks!
There are 10 kind of people on this world: those who understand binary and those who don't!

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
Let's say you have these numbers in the input: 1, 1, and 3 ... (notice there are two ones there) ...

The possible sum is:
1+3 -> 4

Notice that 1+1 -> 2 cannot be used since both numbers are the same. The problem description requires the numbers to be distinct.

So, for input

Code: Select all

``````3
1
1
3
1
2
0``````
The output should be:

Code: Select all

``````Case 1:
Closest sum to 2 is 4.``````
-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong
Turuthok, you are right. But I don't think this kind of input is present in the judge input.
Because my accepted program gives 2 as the answer.

Pier, try this input:
2
1
2
1
2147483647 (MaxInt)
0
The output should be trivial.

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong
For p10490, your perfect number for 31 is wrong.

Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:
Thanks! I got AC on both!
There are 10 kind of people on this world: those who understand binary and those who don't!

Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States
Does anyone know what the range of the integers in the input set is? Can there be negative values?

Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States
If I change my unsigned int's to int's it gets accepted so it seems there are negative values in the input...

yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am
actually, there is no restricttion abt giving only +ve ints.
there may be - ve ints.
in some problem, i think i should check it if even it is not told..
---
anupam

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
i have facad the same problem.
but at first i thought it to be my mistake.
the problem was, i think, "the bases are loaded".
am i right?
"Everything should be made simple, but not always simpler"

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
i use only:

long int data[1005];

How can it be possible to accept this problem in .002 sec.
i ac this problem in .020 sec.

what i have done:

2/ Sort the input data by qsort
3/ Binary search while also adding two data.

is there any possilbe way to minimize time.
__nOi.m....

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
hi turuthok,

3
1
1
3
1
2
0
the ouput of my ac prgram is:
Case 1:
Closest sum to 2 is 2.

what should be the actual answer?
__nOi.m....

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
Output for above input should be 4.

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
hi thoruk,

i manage my program to output the answer as yours.

but the runtime of my program increase a lot.

how can i minimize time.
any sussetion is appricable.
__nOi.m....

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
I can't still solve the problem.
it gives me WA. btu donno why.
Would you please give some critical cases for my program?

here it is.

Code: Select all

``````#include<stdio.h>
#include<math.h>
#define N 1005
main()
{
freopen("in.txt","r",stdin);
long int cas=1,n,i,j,h,m,z,a[N],l,dif,now,pre,b[N];
while(scanf("%ld",&n)!=EOF && n)
{
printf("Case %ld:\n",cas);cas++;
for(i=0;i<n;i++) scanf("%ld",&b[i]);
for(i=0;i<n;i++)
{
h=i;
for(j=i+1;j<n;j++) if(b[j]<b[h]) h=j;
j=b[h];b[h]=b[i];b[i]=j;
}
h=1;a[0]=b[0];
for(i=1;i<n;i++) if(b[i]!=b[i-1]) a[h++]=b[i];n=h;
scanf("%ld",&m);
for(z=0;z<m;z++)
{
scanf("%ld",&l);
dif=pre=abs(a[0]+a[1]-l),now=a[0]+a[1];
for(i=0;i<n;i++)
{
for(j=i+1;j<n && abs(a[i]+a[j]-l)<=pre;j++) pre=abs(a[i]+a[j]-l);
if(pre<dif) dif=pre,now=a[i]+a[j-1];
}
printf("Closest sum to %ld is %ld.\n",l,now);
}
}
return 0;
}``````
simple, first sort, then find distinct numbers, then, just check for the closest. But, why WA??
"Everything should be made simple, but not always simpler"

jamu
New poster
Posts: 13
Joined: Wed Dec 03, 2003 11:15 am
Consider this input:
7
13
19
29
86
73
11
53
4
87
92
43
120
0