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

scor_k
New poster
Posts: 4
Joined: Fri Sep 12, 2008 7:29 pm

Re: 10487 - Closest Sums

Post by scor_k » Thu Oct 09, 2008 4:01 pm

hi mf, i define arr[1005] as a global array, but still run time error. what can i do?

jknisely
New poster
Posts: 2
Joined: Tue Sep 16, 2008 6:35 pm

Re: 10487 - Closest Sums

Post by jknisely » Thu Oct 11, 2012 3:37 am

Hi, this one has me stumped. My code passes all the tests that I can find, but I am still getting WA. Any suggestions would be appreciated.

Code: Select all

#include <cstdio>
#include <algorithm>
typedef long long int lld;
struct SameAsLast {
  lld last;
  SameAsLast(lld l) : last(l) { ; }
  bool operator()(lld x) {
    bool result = (last == x);
    last = x;
    return result;
  }
};

lld absdiff(lld x, lld y) { return ((x<y) ? (y-x) : (x-y)); }

int main() {
  lld curr, best[25], nums[1000], q[25];
  unsigned int k=0,m,M,n,N;
  lld *stop, *a, *b;

  while (1 == scanf("%u", &N) && N) {
    for (n=0; n < N; ++n) {
      if (1 != scanf("%lld", nums+n)) { return 1; }
    }
    std::sort(nums, nums+N);
    stop = std::remove_if(nums+1, nums+N, SameAsLast(nums[0]));
    curr = nums[0] + nums[1];

    if (1 != scanf("%u", &M)) { return 1; }
    for (m=0; m < M; ++m) {
      if (1 != scanf("%lld", q+m)) { return 1; }
      best[m] = curr;
    }

    if (nums+1 == stop) {
      for (m=0; m < M; ++m) { puts("0"); }
    } else {
      for (a=nums; a < stop; ++a) {
        for (b=a+1; b < stop; ++b) {
          curr = *a + *b;
          for (m=0; m < M; ++m) {
            if (absdiff(curr, q[m]) < absdiff(best[m], q[m])) { best[m] = curr; }
          }
        }
      }
      printf("Case %u:\n", ++k);
      for (m=0; m < M; ++m) { printf("Closest sum to %llu is %lld.\n", q[m], best[m]); }
    }

  }
  return 0;
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10487 - Closest Sums

Post by brianfry713 » Fri Oct 12, 2012 11:57 pm

Try input:

Code: Select all

2
5
5
1
10
0
Check input and AC output for thousands of problems on uDebug!

farnaws123
New poster
Posts: 11
Joined: Sun Dec 09, 2012 11:18 pm

Re: 10487 - Closest Sums

Post by farnaws123 » Thu Dec 13, 2012 2:00 am

Code: Select all

#include<iostream>
#include<cstdio>
using namespace std;

/*farnaws,10487,C++*/

int main()
{
	
	int n=0, numbers[1005],m=0,queries[30],temp=0,sum_array_length=0,test_case=0;
	while(1)
	{
		
		cin>>n;
		getchar();
		if(n>1 && n<=1000)
		{
			
				temp=n;
				sum_array_length=0;
				for(int i=0; i<n; i++)
				{		
					cin>>numbers[i];
					sum_array_length=sum_array_length+(--temp);
								
				}
				int sum[sum_array_length];
				int count=0;
				for(int i=0; i<n; i++)
				{	
					for(int j=i+1; j<n; j++)
					{
						
						//if(numbers[i]!=numbers[j])
						//{
							int summation=numbers[i]+numbers[j];
							sum[count]=summation;
							count++;
						//}
					}
				}
				
				cin>>m;
				getchar();
				if(m>0 && m<25)
				{
						for(int i=0; i<m; i++)
						{
							cin>>queries[i];	
						}
						
						cout<<"Case "<<test_case+1<<":"<<endl;
						for(int i=0; i<m; i++)
						{
							int min=100000;
							for(int j=0; j<sum_array_length; j++)
							{
								int diff;
								if(sum[j]>queries[i])
								{
									diff=sum[j]-queries[i];	
								}
								else
								{
								   	diff=queries[i]-sum[j];	
								}
								if(diff<min)
								{
									min=diff;		
								}		
							}
							for(int k=0; k<count; k++)
							{
								if((queries[i]-min)==sum[k] || (queries[i]+min)==sum[k])
								{
									cout<<"Closest sum to "<<queries[i]<<" is "<<sum[k]<<"."<<endl;
									break;
								}	
								
							}
							
						}
						test_case++;
				}
				else
				{
					break;	
				}
		}
		else
		{
			
			break;
		}
	}
	return 0;
}
what's wrong? getting WA, tested for almost al possible inputs

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10487 - Closest Sums

Post by brianfry713 » Fri Dec 14, 2012 1:06 am

Input:

Code: Select all

2
100000
100001
1
1
0
AC output:

Code: Select all

Case 1:
Closest sum to 1 is 200001.
Check input and AC output for thousands of problems on uDebug!

farnaws123
New poster
Posts: 11
Joined: Sun Dec 09, 2012 11:18 pm

Re: 10487 - Closest Sums

Post by farnaws123 » Fri Dec 14, 2012 5:33 am

you're great! Thank you, it worked!!!!!!!=))

Vatyx
New poster
Posts: 1
Joined: Wed Jun 19, 2013 9:30 pm

Re: 10487 - Closest Sums

Post by Vatyx » Wed Jun 19, 2013 9:35 pm

I really need help on this problem. Anything I do, I get WA. Every case posted on this thread works and has the correct output. I keep thinking that it might have something to do with an extra line missing on the output but that doesn't seem to be the case. As stated previously on the thread, duplicate numbers don't exist in the set so I didn't account for them. Please help!!!

Code: Select all

import java.util.*;

class Main{

	public static void main(String[] args) {
		Scanner file = new Scanner(System.in);
		int caseNum = 1;
		while(true){
			int n = file.nextInt();
			if(n == 0){
				System.exit(0);
			}
			int[] set = new int[n];
			for(int i = 0; i < set.length; i++){
				set[i] = file.nextInt();
			}
			int m = file.nextInt();
			int[] que = new int[m];
			for(int i = 0; i < que.length; i++){
				que[i] = file.nextInt();
			}
			if(caseNum != 1){
				System.out.println();
			}
			System.out.println("Case " + caseNum + ":");
			for(int i = 0; i < que.length; i++){
				int closestSum = set[0] + set[1];
				int sum;

				for(int j = 0; j < set.length; j++){
					for(int k = 0; k < set.length; k++){
						if(j != k){
							sum = set[j] + set[k];
							if(Math.abs(que[i] - sum) <= Math.abs(que[i] - closestSum)){
								closestSum = sum;
							}
						}
					}//third for
				}//second for
				System.out.print("Closest sum to " + que[i] + " is " + closestSum + ".");
				if(i != que.length - 1){
					System.out.println();
				}
			}//first for
			caseNum++;
		}//while

	}//main

}//class

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10487 - Closest Sums

Post by brianfry713 » Thu Jun 20, 2013 3:58 am

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

Abdelraoof
New poster
Posts: 1
Joined: Wed Jul 03, 2013 4:16 am

Re: 10487 - Closest Sums

Post by Abdelraoof » Wed Jul 03, 2013 4:22 am

WA.
I have tested a lot of test cases.
Please help.
.....................
Removed (AC) :)

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 10487 - Closest Sums

Post by mahade hasan » Mon Nov 04, 2013 10:15 am

Cutt
Last edited by mahade hasan on Mon Nov 04, 2013 3:03 pm, edited 2 times in total.
we r surrounded by happiness
need eyes to feel it!

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm
Location: Bangladesh

Re: 10487 - Closest Sums

Post by shuvokr » Mon Nov 04, 2013 11:56 am

MAHADE_HASAN Try this input:
Input:

Code: Select all


3
6
5
4
1
111

Code: Select all

enjoying life ..... 

kat
New poster
Posts: 3
Joined: Thu May 30, 2013 6:53 pm

Re: 10487 - Closest Sums

Post by kat » Fri Jan 17, 2014 9:03 pm

Be Careful about That Inputs:

Code: Select all

Input:
5
3 12 17 33 34
3
42 46 49
5
3 12 17 33 34
3
42 46 47
Output:
Case 1:
Closest sum to 42 is 45.
Closest sum to 46 is 46.
Closest sum to 49 is 50.
Case 2:
Closest sum to 42 is 45.
Closest sum to 46 is 46.
Closest sum to 47 is 46.
Because,you have to find a sum of two distinct numbers from the set, which is closest to the query number.49 is close to 50 & 47 is close to 46.

TLEorWA
New poster
Posts: 12
Joined: Sat Mar 01, 2014 12:56 pm

Re: 10487 - Closest Sums

Post by TLEorWA » Thu Mar 27, 2014 3:08 am

Why Runtime Error :( help...
here is my code -

REmoved after ac.

Thanks brianfry713 :D
Last edited by TLEorWA on Thu Mar 27, 2014 9:54 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10487 - Closest Sums

Post by brianfry713 » Thu Mar 27, 2014 8:04 pm

1000 choose 2 = 499500, your array sum[100000] is too small.
Check input and AC output for thousands of problems on uDebug!

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10487 - Closest Sums

Post by uDebug » Tue Apr 29, 2014 1:31 pm

Replying to follow the thread.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Post Reply

Return to “Volume 104 (10400-10499)”