10487 - Closest Sums
Moderator: Board moderators
-
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
-
- Experienced poster
- Posts: 209
- Joined: Sun Jan 16, 2005 6:22 pm
hi similitude
your can simplify ur qsort().
i think its much easier to code.
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;}
-
- New poster
- Posts: 30
- Joined: Mon Jun 19, 2006 10:37 pm
- Contact:
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;
}
win
Got WA too.
Could anybody help me, please?
I've passed all the test cases I found...
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.
Re: 10487 - Closest Sums
for this input
the output should be
not this
and after correcting that your code will fail for this
which should be
Best wishes!
EDIT :: even if your program outputs 8 for the first input, you'll get AC! that means, all the inputs will be distinct, so there will be no such inputs!
Code: Select all
3
3
5
5
1
10
Code: Select all
Case 1:
Closest sum to 10 is 10.
Code: Select all
Case 1:
Closest sum to 10 is 8.
Code: Select all
3
5
6
5
1
20
Code: Select all
Case 1:
Closest sum to 20 is 11.
EDIT :: even if your program outputs 8 for the first input, you'll get AC! that means, all the inputs will be distinct, so there will be no such inputs!
fahim
#include <smile.h>
#include <smile.h>
-
- New poster
- Posts: 37
- Joined: Wed Oct 03, 2007 10:42 am
Re: 10487 - Closest Sums
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.
-
- Experienced poster
- Posts: 162
- Joined: Thu Jul 13, 2006 7:07 am
- Location: Campus Area. Dhaka.Bangladesh
- Contact:
Re: 10487 - Closest Sums
I tried all test case but and output is okey but WA.
Why? I need some more input.
here is my code:
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;
}
http://www.newton.0fees.net is enough!
Re: 10487 - Closest Sums
BSearch function in your code is not correct. Think about it & judge this case:
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.
Code: Select all
3
1
7
10
1
16
Hope it helps.
Solving for fun..
-
- Experienced poster
- Posts: 162
- Joined: Thu Jul 13, 2006 7:07 am
- Location: Campus Area. Dhaka.Bangladesh
- Contact:
Re: 10487 - Closest Sums
For that case what would be the output?
is it 3 or 5?
Code: Select all
3
1
2
4
1
4
http://www.newton.0fees.net is enough!
-
- Experienced poster
- Posts: 103
- Joined: Tue Mar 25, 2008 11:00 pm
- Location: IUT-OIC, DHAKA, BANGLADESH
- Contact:
Re: 10487 - Closest Sums
My AC gives
uvatoolkit gives
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
Code: Select all
Case 1:
Closest sum to 4 is 3.
Code: Select all
Case 1:
Closest sum to 4 is 5.
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...............................
It is more tough to become a good person.
I am trying both...............................
-
- Experienced poster
- Posts: 162
- Joined: Thu Jul 13, 2006 7:07 am
- Location: Campus Area. Dhaka.Bangladesh
- Contact:
Re: 10487 - Closest Sums
I am sorry.
There was a line in problem specification that no input will be given for wich there is duplicate answer.
Thank you.
There was a line in problem specification that no input will be given for wich there is duplicate answer.
Thank you.
http://www.newton.0fees.net is enough!
Re: 10487 - Closest Sums
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;
}
#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;
}
Re: 10487 - Closest Sums
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).