10487 - Closest Sums

[scor_k]

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

[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]

Try input:

Code: Select all

2
5
5
1
10
0

[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]

Input:

Code: Select all

2
100000
100001
1
1
0

AC output:

Code: Select all

Case 1:
Closest sum to 1 is 200001.

[farnaws123]

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

[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]

Doesn't match the sample I/O.

[Abdelraoof]

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

[mahade hasan]

Cutt

[shuvokr]

MAHADE_HASAN Try this input:
Input:

Code: Select all

3
6
5
4
1
111

[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]

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

REmoved after ac.

Thanks brianfry713

[brianfry713]

1000 choose 2 = 499500, your array sum[100000] is too small.

[uDebug]

Replying to follow the thread.