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

hi mf, i define arr 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

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, nums, q;
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));
curr = nums + nums;

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

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

Code: Select all

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

/*farnaws,10487,C++*/

int main()
{

int n=0, numbers,m=0,queries,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

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

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

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

Re: 10487 - Closest Sums

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 + set;
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

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

WA.
I have tested a lot of test cases.
.....................
Removed (AC) Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 10487 - Closest Sums

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

Re: 10487 - Closest Sums

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

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

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

REmoved after ac.

Thanks brianfry713 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

1000 choose 2 = 499500, your array sum 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