10487 - Closest Sums

[Pier]

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!

[turuthok]

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-

[Eric]

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]

For p10490, your perfect number for 31 is wrong.

[Pier]

Thanks! I got AC on both!

[rjhadley]

Does anyone know what the range of the integers in the input set is? Can there be negative values?

[rjhadley]

If I change my unsigned int's to int's it gets accepted so it seems there are negative values in the input...

[yahoo]

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]

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?

[Noim]

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:

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.

[Noim]

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?

[turuthok]

Output for above input should be 4.

-turuthok-

[Noim]

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.

[anupam]

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

[jamu]

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.