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

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!

rjhadley
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?

rjhadley
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
Location: Bangladesh
i use only:

long int data;

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

what i have done:

1/ Read input
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
Location: Bangladesh
hi turuthok,

for your input:
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
Location: Bangladesh
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=b;
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+a-l),now=a+a;
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
your program gives:
Case 1:
Closest sum to 87 is 84.
Closest sum to 92 is 97.
Closest sum to 43 is 40.
Closest sum to 120 is 126.
and my AC program gives something else:
Case 1:
Closest sum to 87 is 86.
Closest sum to 92 is 92.
Closest sum to 43 is 42.
Closest sum to 120 is 115.