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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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

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 »

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 »

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 »

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 »

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 »

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

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

Re: 10487 - Closest Sums

Post by uDebug »

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)”