![:cry:](./images/smilies/icon_cry.gif)
10487 - Closest Sums
Moderator: Board moderators
-
- Experienced poster
- Posts: 131
- Joined: Sat Jul 17, 2004 4:09 am
- Location: Lima, Per
-
- Experienced poster
- Posts: 131
- Joined: Sat Jul 17, 2004 4:09 am
- Location: Lima, Per
10487 WA- I don't know why.
This is my code:
#include <stdio.h>
long t,akt;
long tab[1001];
int n,m,c,i;
void licz(long co);
void sortowanie(int p, int k);
void uprosc();
int main()
{
c=0;
while (1==1)
{
scanf("%d",&n);
if (n==0)
return 0;
c++;
for (i=1;i<=n;i++)
scanf("%d",&tab);
sortowanie(1,n);
uprosc();
scanf("%d",&m);
printf("Case %d:\n",c);
for (i=1;i<=m;i++)
{
scanf("%d",&t);
printf("Closest sum to %d is ",t);
if (n>1)
licz(t);
else
printf("0.\n");
}
}
return 0;
}
long abs(long co)
{
if (co<0)
co=-co;
return co;
}
long szukaj(long co)
{
long p=1,k=n-1,poz;
long best;
poz=1;
if (poz==akt)
poz++;
if (co<=tab[poz])
return tab[poz];
poz=n;
if (poz==akt)
poz--;
if (co>=tab[poz])
return tab[poz];
while (1==1)
{
poz=(p+k)/2;
if ((tab[poz]<=co) && (tab[poz+1]>=co))
break;
if (co<tab[poz])
k=poz-1;
else
p=poz+1;
}
if (tab[poz]==akt)
{
best=tab[poz+1];
if (poz>2)
{
if ((co-abs(tab[poz-1]))<(co-best))
best=tab[poz-1];
}
return best;
}
if (tab[poz+1]==akt)
{
best=tab[poz];
if (poz<n)
{
if ((co-abs(tab[poz+1]))<(co-best))
best=tab[poz+1];
}
return best;
}
if (abs(co-tab[poz])<=abs(co-tab[poz+1]))
return tab[poz];
else
return tab[poz+1];
}
void licz(long co)
{
long suma,t;
akt=1;
suma=szukaj(co-tab[1])-co+tab[1];
for (int i=2;i<=n;i++)
{
akt=i;
t=szukaj(co-tab)-co+tab;
if (abs(t)<abs(suma))
suma=t;
if (suma==0)
break;
}
printf("%d.\n",co+suma);
}
void zamiana(int a, int b)
{
long t;
t=tab[a];
tab[a]=tab;
tab=t;
}
void sortowanie(int p,int k)
{
if (p<k)
{
int m=p;
for (int i=p+1;i<=k;i++)
if (tab<tab[p])
zamiana(i,++m);
zamiana(p,m);
sortowanie(p,m-1);
sortowanie(m+1,k);
}
}
void uprosc()
{
int k=1;
for (int i=2;i<=n;i++)
if (tab!=tab[k])
{
k++;
zamiana(i,k);
}
n=k;
}
if anybody see any mistakes please help me!!!!![/code]
#include <stdio.h>
long t,akt;
long tab[1001];
int n,m,c,i;
void licz(long co);
void sortowanie(int p, int k);
void uprosc();
int main()
{
c=0;
while (1==1)
{
scanf("%d",&n);
if (n==0)
return 0;
c++;
for (i=1;i<=n;i++)
scanf("%d",&tab);
sortowanie(1,n);
uprosc();
scanf("%d",&m);
printf("Case %d:\n",c);
for (i=1;i<=m;i++)
{
scanf("%d",&t);
printf("Closest sum to %d is ",t);
if (n>1)
licz(t);
else
printf("0.\n");
}
}
return 0;
}
long abs(long co)
{
if (co<0)
co=-co;
return co;
}
long szukaj(long co)
{
long p=1,k=n-1,poz;
long best;
poz=1;
if (poz==akt)
poz++;
if (co<=tab[poz])
return tab[poz];
poz=n;
if (poz==akt)
poz--;
if (co>=tab[poz])
return tab[poz];
while (1==1)
{
poz=(p+k)/2;
if ((tab[poz]<=co) && (tab[poz+1]>=co))
break;
if (co<tab[poz])
k=poz-1;
else
p=poz+1;
}
if (tab[poz]==akt)
{
best=tab[poz+1];
if (poz>2)
{
if ((co-abs(tab[poz-1]))<(co-best))
best=tab[poz-1];
}
return best;
}
if (tab[poz+1]==akt)
{
best=tab[poz];
if (poz<n)
{
if ((co-abs(tab[poz+1]))<(co-best))
best=tab[poz+1];
}
return best;
}
if (abs(co-tab[poz])<=abs(co-tab[poz+1]))
return tab[poz];
else
return tab[poz+1];
}
void licz(long co)
{
long suma,t;
akt=1;
suma=szukaj(co-tab[1])-co+tab[1];
for (int i=2;i<=n;i++)
{
akt=i;
t=szukaj(co-tab)-co+tab;
if (abs(t)<abs(suma))
suma=t;
if (suma==0)
break;
}
printf("%d.\n",co+suma);
}
void zamiana(int a, int b)
{
long t;
t=tab[a];
tab[a]=tab;
tab=t;
}
void sortowanie(int p,int k)
{
if (p<k)
{
int m=p;
for (int i=p+1;i<=k;i++)
if (tab<tab[p])
zamiana(i,++m);
zamiana(p,m);
sortowanie(p,m-1);
sortowanie(m+1,k);
}
}
void uprosc()
{
int k=1;
for (int i=2;i<=n;i++)
if (tab!=tab[k])
{
k++;
zamiana(i,k);
}
n=k;
}
if anybody see any mistakes please help me!!!!![/code]
NOthing special
10487 WA
Hrrrmmm. Why am I getting WA? I've read all the other posts for this problem.. nothing helps ![:(](./images/smilies/icon_frown.gif)
Thanks! ![:)](./images/smilies/icon_smile.gif)
- Andrew
![:(](./images/smilies/icon_frown.gif)
Code: Select all
code removed after AC :)
![:)](./images/smilies/icon_smile.gif)
- Andrew
10487 how to use binary search
1. input data
2. sort them(qsort)
3. binary search
but how do I use binary search to find the closest sum
Could somebody give me some example or pusedo code
Cause I don't want to code my program so messly
Give me direction and pusedo code
Thanks for your reply
2. sort them(qsort)
3. binary search
but how do I use binary search to find the closest sum
Could somebody give me some example or pusedo code
Cause I don't want to code my program so messly
Give me direction and pusedo code
Thanks for your reply
There can be at most 1000 numbers. So, number of (sum of 2 distinct terms) is less than (1000*1000/2+1).
First store all the possible sums. Then you can use linear search.
First store all the possible sums. Then you can use linear search.
Ami ekhono shopno dekhi...
HomePage
HomePage
I still got WA :'(
I passed all tests posted on the board, but it's still WA :'( (also switched from bin-search to linear), please help me
Code: Select all
Aced
Last edited by FAQ on Fri Mar 24, 2006 12:38 pm, edited 1 time in total.
I think your code is not right. Try the following i/o set...
Input:
Output:
Hope it helps.
Input:
Code: Select all
5
1
3
7
10
12
6
3
4
5
6
10
12
0
Code: Select all
Case 1:
Closest sum to 3 is 4.
Closest sum to 4 is 4.
Closest sum to 5 is 4.
Closest sum to 6 is 4.
Closest sum to 10 is 10.
Closest sum to 12 is 11.
Ami ekhono shopno dekhi...
HomePage
HomePage
Still some errors. Try the following i/o set...
Input:
Output:
And the spelling is 'Closest', not 'Closet'.
Hope it helps.
Input:
Code: Select all
3
3
5
5
1
10
0
Code: Select all
Case 1:
Closest sum to 10 is 8.
![:D](./images/smilies/icon_biggrin.gif)
Hope it helps.
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- Experienced poster
- Posts: 136
- Joined: Fri Apr 15, 2005 3:47 pm
- Location: Singapore
- Contact:
Why WA ???
Code: Select all
ACed...
10487 - WA WA WA - need test cases
After 14 submissions and 14 consecutive failure... i am so tired...
Can you tell me what is wrong here ?
Or can anyone give me some effective testcases ...
p-l-e-a-s-e ?
I tried every topic avialable at e-board, none could give me the soln.
Can you tell me what is wrong here ?
Or can anyone give me some effective testcases ...
p-l-e-a-s-e ?
Code: Select all
/*
* 10487 closest sum
* submission 1 RE 2 RE 3 RE 4 RE 5 WA
* coded at 8:09am, april 13, 2006
*
*/
#include <stdio.h>
#include <stdlib.h>
long long sum[1000000];
long long myabs(long long x) {
return (x>0) ? x : (-1*x);
}
int comp(const void *a, const void *b) {
long long *x=(long long *)a;
long long *y=(long long *)b;
if(*x>*y) return 1;
if(*x<*y) return -1;
else return 0;
}
long long search(long long num,long long range) {
long long i;
long long min=100000000;
long long ans;
for(i=0;i<=range;i++) {
if(myabs(num-sum[i])<min) {
min=myabs(num - sum[i]);
ans=sum[i];
}else if(myabs(num-sum[i])>min ) break;
}
return ans;
}
int main() {
long long input[1005];
long long n,m;
long long i,j,k;
long long query;
long long cases=0;
while(scanf("%d",&n)==1) {
if(n==0) break;
for(i=0;i<n;i++) {
scanf("%d",&input[i]);
}
k=-1;
for(i=0;i<n;i++) {
for(j=i+1;j<n;j++) {
if(input[i]==input[j]) continue;
sum[++k]= input[i] + input[j];
}
}
qsort(sum,k+1,sizeof(sum[0]),comp);
scanf("%d",&m);
printf("Case %d:\n",++cases);
for(i=0;i<m;i++) {
scanf("%d",&query);
printf("Closest sum to %d is %d.\n",query,search(query,k));
}
}
return 0;
}
fahim
#include <smile.h>
#include <smile.h>