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

User avatar
Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:

Post by Pier » Fri May 09, 2003 6:40 pm

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:

Post by turuthok » Fri May 09, 2003 8:47 pm

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

Post by Eric » Sat May 10, 2003 4:49 am

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

Post by Eric » Sat May 10, 2003 4:56 am

For p10490, your perfect number for 31 is wrong. :wink:

User avatar
Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:

Post by Pier » Sun May 11, 2003 6:31 am

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

Post by rjhadley » Wed May 21, 2003 6:44 am

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

Post by rjhadley » Wed May 21, 2003 7:44 am

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

User avatar
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

Post by yahoo » Wed May 21, 2003 9:43 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:

Post by anupam » Wed May 21, 2003 9:51 am

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

Post by Noim » Sat Jun 07, 2003 4:44 pm

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.
__nOi.m....

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Location: Bangladesh

Post by Noim » Sat Jun 07, 2003 4:53 pm

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.
:o

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

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Sat Jun 07, 2003 9:21 pm

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

Post by Noim » Sun Jun 08, 2003 6:46 am

hi thoruk,

i manage my program to output the answer as yours.

but the runtime of my program increase a lot. :cry:

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

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Fri Jul 02, 2004 2:48 pm

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

Post by jamu » Fri Jul 09, 2004 10:45 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.

Post Reply

Return to “Volume 104 (10400-10499)”