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
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Thu Apr 13, 2006 5:20 am

I dont know, why i used long long, i tried to figure out all the possibilites to get ac.
fahim
#include <smile.h>

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Apr 13, 2006 9:45 am

You can't read and write long longs with "%d", you should use "%lld" instead.
Alternatively replace all your long longs by ints.
Either way, you'll get accepted.

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Sat Apr 15, 2006 9:53 am

shame on me! :oops:
fahim
#include <smile.h>

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Tue Jun 13, 2006 10:09 am

hi similitude

your can simplify ur qsort().

Code: Select all

qsort(num,n,sizeof(int),(int(*)(const void *,const void *)) comp);

int comp(const int *i,const int *j){return *i-*j;}

i think its much easier to code.
:)

vinit_iiita
New poster
Posts: 30
Joined: Mon Jun 19, 2006 10:37 pm
Contact:

Post by vinit_iiita » Thu Aug 10, 2006 10:05 pm


hi freinds i got re twice i cannot figure out why plz help me...

Code: Select all

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    int j=1;
    while (cin>>n && n!=0)
    {
          int a[n];
          for (int i=0;i<n;i++) 
          cin>>a[i];
          
          vector<long long int> v;
          for (int i=0;i<n;i++)
          {
              for (int k=i+1;k<n;k++)
              {
                  if (a[i]!=a[k])
                  {int t=a[i]+a[k];
                   v.push_back(t);
                   }
                  }
                  }
                  sort(v.begin(),v.end());
         
             
          int nq;
          cin>>nq;
          cout<<"Case "<<j<<":"<<endl;
          for (int i=0;i<nq;i++)
          {
              long long int q;
              cin>>q;
              int k=0;
               while (v[k]<q)
               {
                     k++;
               }
           
            if ((v[k]-q)<=(q-v[k-1]) || k==0)
            cout<<"Closest sum to "<<q<<" is "<<v[k]<<"."<<endl;
            else
            cout<<"Closest sum to "<<q<<" is "<<v[k-1]<<"."<<endl;
           
               }
               j++;
               }          
              return 0;
              }
              
              
          
          
thanx in advance..[/b]
win

User avatar
WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:

Post by WingletE » Fri Aug 17, 2007 5:12 am

Got WA too.
Could anybody help me, please?
I've passed all the test cases I found...

Code: Select all

removed after AC
Last edited by WingletE on Thu Jul 02, 2009 2:23 pm, edited 1 time in total.

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Re: 10487 - Closest Sums

Post by smilitude » Tue Jul 01, 2008 9:33 pm

for this input

Code: Select all

3
3
5
5
1
10
the output should be

Code: Select all

Case 1:
Closest sum to 10 is 10.
not this

Code: Select all

Case 1:
Closest sum to 10 is 8.
and after correcting that your code will fail for this

Code: Select all

3
5
6
5
1
20
which should be

Code: Select all

Case 1:
Closest sum to 20 is 11.
:) Best wishes!

EDIT :: even if your program outputs 8 for the first input, you'll get AC! :P that means, all the inputs will be distinct, so there will be no such inputs!
fahim
#include <smile.h>

alamgir kabir
New poster
Posts: 37
Joined: Wed Oct 03, 2007 10:42 am

Re: 10487 - Closest Sums

Post by alamgir kabir » Sun Jul 20, 2008 8:34 pm

Code: Select all

code removed after acc
Last edited by alamgir kabir on Tue Apr 21, 2009 9:24 pm, edited 1 time in total.

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Re: 10487 - Closest Sums

Post by newton » Fri Jul 25, 2008 10:27 am

I tried all test case but and output is okey but WA.
Why? I need some more input.
here is my code:

Code: Select all

#include <stdio.h>
#include <algorithm>
#define INF 1<<29
#define MAX 1001


using namespace std;

long int array[MAX];
long int sum[MAX*(MAX-1)/2];

long int BSearch(long int N,long int key){
	long int beg = 0;
	long int end = N;
	long int mid = (beg + end)/2;
	
	while(end >= beg){
		if(sum[mid] == key)
			break;
		if(sum[mid] < key)
			beg = mid + 1;
		else
			end = mid - 1;
		mid = (beg + end)/2;
	}				
	return mid;	
}

int main(){
	long int N,Q,query,i,j,value,c = 1;
	//freopen("in.txt","rt",stdin);
	
	while(scanf("%ld",&N)==1 && N){
		for(i = 0; i< N; i++)
			scanf("%ld",&array[i]);
		int k = 0;
		for(i = 0; i < N; i++){
			for(j = i + 1; j < N; j++)
				sum[k++] = array[i] + array[j];
		}
		sort(sum,sum+k);
		
		scanf("%ld",&Q);
		printf("Case %ld:\n",c++);
		for(i = 0; i < Q; i++){
			scanf("%ld",&query);				
			value = BSearch(k-1,query);			
			printf("Closest sum to %ld is %ld.\n",query,sum[value]);
		}
	}
	return 0;
}

User avatar
linux
Learning poster
Posts: 56
Joined: Sat Jul 01, 2006 12:21 pm
Location: CA-95054
Contact:

Re: 10487 - Closest Sums

Post by linux » Thu Jul 31, 2008 8:56 am

BSearch function in your code is not correct. Think about it & judge this case:

Code: Select all

3
1
7
10
1
16
Try to think about correctness of your algorithms and segments first when writing programs. Hence, generating Input/Output set for yourself is easier than others.
Hope it helps.
Solving for fun..

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Re: 10487 - Closest Sums

Post by newton » Thu Aug 14, 2008 10:41 pm

For that case what would be the output?

Code: Select all

3
1
2
4
1
4
is it 3 or 5?

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 10487 - Closest Sums

Post by kbr_iut » Mon Aug 18, 2008 2:29 am

My AC gives

Code: Select all

Case 1:
Closest sum to 4 is 3.
uvatoolkit gives

Code: Select all

Case 1:
Closest sum to 4 is 5.
that means both of them r correct.dont b tensed about that.

note: If u need output for any input set go to this link.
http://uvatoolkit.com/
it generates output for any input set of uva problems.
hope it helps
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Re: 10487 - Closest Sums

Post by newton » Mon Aug 18, 2008 8:44 am

I am sorry.
There was a line in problem specification that no input will be given for wich there is duplicate answer.
Thank you.

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

Re: 10487 - Closest Sums

Post by scor_k » Mon Oct 06, 2008 7:54 pm

i m getting always rte. please ....help me.please,,please


#include<stdio.h>
#include<math.h>
#define X 1000000
int main()
{

long int n,m,arr[X],brr[X],i,j,p,t,s,a,b,sum,sub,crr[X],l,q,r,cas=0;

while(1)
{
scanf("%ld",&n);

cas++;

if(n==0)
break;


for(i=0;i<n;i++)
{

scanf("%ld",&arr);
}

scanf("%ld",&m);

for(j=0;j<m;j++)
{
scanf("%ld",&brr[j]);
}

t=0;


for(a=0;a<n;a++)
{
for(b=a+1;b<n;b++)
{

if(arr[a]!=arr)
sum=arr[a]+arr;

crr[t]=sum;
t++;

}


}

printf("Case %ld:\n",cas);

for(l=0;l<m;l++)
{
s=X;
for(q=0;q<t;q++)
{
sub=(crr[q]-brr[l]);

if(sub<0)
{

sub=sub*(-1);
}


if(s>sub)
{
s=sub;
r=crr[q];
}

}

printf("Closest sum to %ld is %ld.\n",brr[l],r);

}


}
return 0;
}

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10487 - Closest Sums

Post by mf » Mon Oct 06, 2008 9:22 pm

It doesn't seem to me like a good idea to keep many-megabyte-long arrays on the stack. Make them static, global, or allocate memory for them from the heap (with malloc).

Post Reply

Return to “Volume 104 (10400-10499)”