855  Lunch in Grid City
Moderator: Board moderators

 Learning poster
 Posts: 71
 Joined: Thu Aug 21, 2003 1:56 am
855  Lunch in Grid City
I must be braindead. I cannot see why my program gives WA:
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b)
{
return *(int *)a  *(int *)b;
}
int main(void)
{
int T, F;
int s[50000], a[50000];
int i;
int meds, meda;
scanf("%d\n", &T);
while (T > 0) {
scanf("%*d %*d %d", &F);
for (i = 0; i < F; i++) {
scanf("%d %d", s+i, a+i);
}
qsort(s, F, sizeof(int), cmp);
qsort(a, F, sizeof(int), cmp);
if (F % 2) {
meds = s[F/2];
meda = a[F/2];
} else {
meds = (s[F/21]+s[F/2])/2;
meda = (a[F/21]+a[F/2])/2;
}
printf("(Street: %d, Avenue: %d)\n", meds, meda);
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b)
{
return *(int *)a  *(int *)b;
}
int main(void)
{
int T, F;
int s[50000], a[50000];
int i;
int meds, meda;
scanf("%d\n", &T);
while (T > 0) {
scanf("%*d %*d %d", &F);
for (i = 0; i < F; i++) {
scanf("%d %d", s+i, a+i);
}
qsort(s, F, sizeof(int), cmp);
qsort(a, F, sizeof(int), cmp);
if (F % 2) {
meds = s[F/2];
meda = a[F/2];
} else {
meds = (s[F/21]+s[F/2])/2;
meda = (a[F/21]+a[F/2])/2;
}
printf("(Street: %d, Avenue: %d)\n", meds, meda);
}
return 0;
}
Pleaseeeee Help Me
I solved this problem in two ways but every time I got WA.Here is my source,my algorithm is dynamic,at first step I found the total distance from all points to (1,1) and then for every other points ,I find the distance
by the point just before it(it is a distance for last point+number of points in right side of the recent point  number of points left side the recent point) the distance with the recent point and points in it's right side decrease 1,in it's left side increase 1.
[cpp]
#include <iostream>
#include <string>
using namespace std;
#define int long long
int a,b,f,m[1001][1001],r[1001],l[1001],u[1001],d[1001];
int main()
{
int mm;
cin>>mm;
for(int tt=0;tt<mm;tt++)
{
cin>>a>>b>>f;
memset(m,0,sizeof m);
memset(r,0,sizeof r);
memset(l,0,sizeof l);
memset(u,0,sizeof u);
memset(d,0,sizeof d);
int s=0;
for(int i=0;i<f;i++)
{
int x,y;
cin>>x>>y;
m[x1][y1]=1;
s+=x1+y1;
}
int g[1001];
memset(g,0,sizeof g);
for(int i=0;i<b;i++)
for(int j=0;j<a;j++)
{
g+=m[j];
}
l[0]=0;
for(int i=1;i<b;i++)
{
l=l[i1]+g[i1];
}
for(int i=b1;i>=0;i)
r+=fl;
/* for(int i=0;i<b;i++)
cout<<" righ "<<i<<" : "<<r;
cout<<endl;
for(int i=0;i<b;i++)
cout<<" left "<<i<<" : "<<l;
cout<<endl;*/
memset(g,0,sizeof g);
for(int i=0;i<a;i++)
for(int j=0;j<b;j++)
{
g+=m[j];
}
u[0]=0;
for(int i=1;i<a;i++)
u+=u[i1]+g[i1];
d[a1]=g[a1];
for(int i=a2;i>=0;i)
d[i]=fu[i];
int mini=s;
int x=0,y=0;
int dis[1001];
dis[0]=s;
for(int i=1;i<a;i++)
{
dis[i]=dis[i1]+u[i]d[i];
}
int dd[1001];
for(int i=0;i<a;i++)
{
dd[0]=dis[i];
if(dis[i]<mini && m[i][0]==1)
{
mini=dis[i];
x=i;
y=0;
}
for(int j=1;j<b;j++)
{
dd[j]=dd[j1]+l[j]r[j];
if(dd[j]<mini && m[i][j]==1)
{
mini=dd[j];
x=i;
y=j;
}
}
}
cout<<"(Street: "<<x+1<<", Avenue: "<<y+1<<")"<<endl;
}
return 0;
}
Pleeeeeeeeeese HELP ME
Is there anyone solved this problem with sorting methode(and writhing the middle element of the sorted array)???[/cpp]
by the point just before it(it is a distance for last point+number of points in right side of the recent point  number of points left side the recent point) the distance with the recent point and points in it's right side decrease 1,in it's left side increase 1.
[cpp]
#include <iostream>
#include <string>
using namespace std;
#define int long long
int a,b,f,m[1001][1001],r[1001],l[1001],u[1001],d[1001];
int main()
{
int mm;
cin>>mm;
for(int tt=0;tt<mm;tt++)
{
cin>>a>>b>>f;
memset(m,0,sizeof m);
memset(r,0,sizeof r);
memset(l,0,sizeof l);
memset(u,0,sizeof u);
memset(d,0,sizeof d);
int s=0;
for(int i=0;i<f;i++)
{
int x,y;
cin>>x>>y;
m[x1][y1]=1;
s+=x1+y1;
}
int g[1001];
memset(g,0,sizeof g);
for(int i=0;i<b;i++)
for(int j=0;j<a;j++)
{
g+=m[j];
}
l[0]=0;
for(int i=1;i<b;i++)
{
l=l[i1]+g[i1];
}
for(int i=b1;i>=0;i)
r+=fl;
/* for(int i=0;i<b;i++)
cout<<" righ "<<i<<" : "<<r;
cout<<endl;
for(int i=0;i<b;i++)
cout<<" left "<<i<<" : "<<l;
cout<<endl;*/
memset(g,0,sizeof g);
for(int i=0;i<a;i++)
for(int j=0;j<b;j++)
{
g+=m[j];
}
u[0]=0;
for(int i=1;i<a;i++)
u+=u[i1]+g[i1];
d[a1]=g[a1];
for(int i=a2;i>=0;i)
d[i]=fu[i];
int mini=s;
int x=0,y=0;
int dis[1001];
dis[0]=s;
for(int i=1;i<a;i++)
{
dis[i]=dis[i1]+u[i]d[i];
}
int dd[1001];
for(int i=0;i<a;i++)
{
dd[0]=dis[i];
if(dis[i]<mini && m[i][0]==1)
{
mini=dis[i];
x=i;
y=0;
}
for(int j=1;j<b;j++)
{
dd[j]=dd[j1]+l[j]r[j];
if(dd[j]<mini && m[i][j]==1)
{
mini=dd[j];
x=i;
y=j;
}
}
}
cout<<"(Street: "<<x+1<<", Avenue: "<<y+1<<")"<<endl;
}
return 0;
}
Pleeeeeeeeeese HELP ME
Is there anyone solved this problem with sorting methode(and writhing the middle element of the sorted array)???[/cpp]

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Re: Pleaseeeee Help Me
Yes, that's the way to do it. Basically it's a two dimensional 'Vito's Family' (I just remember the title of the problem, not the number). In the discussion of that problem on the board, there is an excellent explanation (by Whinii F., if I'm correct) why the median method works in these cases.go wrote: Is there anyone solved this problem with sorting methode(and writhing the middle element of the sorted array)???
So what's wrong with howardchengs's algorithm?
I don't talk about array size, integer type and so on  just the algorithm.
added Nov 22
Perhaps somebody can tell me what's wrong with my program?
I don't talk about array size, integer type and so on  just the algorithm.
added Nov 22
Perhaps somebody can tell me what's wrong with my program?
Code: Select all
#include <stdio.h> /* scanf, printf */
#include <stdlib.h> /* qsort */
/*******************************
* ACM Contest  Problem 855 *
* WA *
*******************************/
long STREETS[50002];
long AVENUES[50002];
int cmp(const void *ap, const void *bp)
{
long a = *(long *)ap;
long b = *(long *)bp;
if (a < b) return 1;
if (a > b) return 1;
return 0;
}
int main(void)
{
int nc, cases;
int ns, streets;
int na, avenues;
int nf, friends;
long medst;
long medav;
scanf("%d",&cases);
for (nc=0;nc<cases;nc++){
scanf("%d %d %d",&streets,&avenues,&friends);
for (nf=0;nf<friends;nf++)
scanf("%ld %ld",&STREETS[nf],&AVENUES[nf]);
if (friends == 1){
medst = STREETS[0];
medav = AVENUES[0];
}
else if (friends == 2){
medst = (STREETS[0]+STREETS[1])/2;
medav = (AVENUES[0]+AVENUES[1])/2;
}
else{
qsort(STREETS,friends,sizeof(long),cmp);
qsort(AVENUES,friends,sizeof(long),cmp);
if ((friends % 2) == 0){
medst = (STREETS[friends/2]+STREETS[friends/21])/2;
medav = (AVENUES[friends/2]+AVENUES[friends/21])/2;
}
else{
medst = STREETS[friends/2];
medav = AVENUES[friends/2];
}
}
printf("(Street: %ld, Avenue: %ld)\n",medst,medav);
}
return 0;
}

 New poster
 Posts: 18
 Joined: Wed Jul 21, 2004 5:09 pm
 Contact:
855  WA
Code: Select all
#include <stdio.h>
#define MAXN 1000
int median(int a[], int n) /* a[i] <= MAX_VAL */
{
int i, sum, m;
sum = 0;
i = 1;
m = (n % 2 == 0 ? (n / 2  1) : n / 2);
while (sum < m) {
sum += a[i];
i++;
}
return i;
}
void init(int a[], int n)
{
int i;
for(i = 1; i <= n; i++)
a[i] = 0;
}
int main()
{
int y[MAXN + 1];
int x[MAXN + 1];
int T, A, S, F;
int median_x, median_y;
int i;
int street, avenue;
scanf("%d", &T);
for(; T > 0; T) {
scanf("%d %d %d", &S, &A, &F);
init(x, A);
init(y, S);
for(i = 0; i < F; i++) {
scanf("%d %d", &street, &avenue);
y[street]++;
x[avenue]++;
}
median_x = median(x, F);
median_y = median(y, F);
printf("(Street: %d, Avenue: %d)\n", median_y, median_x);
}
return 0;
}

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
How does your median work?
You can solve this problem by sorting too, it's fast enough.
You can solve this problem by sorting too, it's fast enough.
Check out http://www.algorithmist.com !

 Learning poster
 Posts: 70
 Joined: Sat Feb 05, 2005 9:38 am
 Location: Gurukul
Help
Hi Yaron,
I think your median function does not always give right answer for all cases. You can sort street and avenue and then just print out the median (Simple Median Knowledge n/2 or n/21). Bye.
I think your median function does not always give right answer for all cases. You can sort street and avenue and then just print out the median (Simple Median Knowledge n/2 or n/21). Bye.
Some Love Stories Live Forever ....
I got Accepted after several wrong answers. And finally I found the bug
in my code.
My algorithm is simple....
in my code.
My algorithm is simple....
Code: Select all
1. First sort the streets.
2. Sort the avenues.
3. Suppose they are in an array p[][2],
p[][0] is the street number, p[][1] is the avenue number
starting from 1 to n (n is the total number)
4. If n is odd assign j < (n+1)/2
5. Otherwise assign j < n/2
6. Print p[j][0] and p[j][1]......
Ami ekhono shopno dekhi...
HomePage
HomePage
i think i'm doing the same thing but still getting wrong answer. here is my sample input and output:
is there anything tricky? please help me!
Code: Select all
22 22 6
1 5
1 4
1 3
2 1
3 10
3 9
Code: Select all
(Street: 1, Avenue: 5)
Code: Select all
10 10 1
5 5
Code: Select all
(Street: 5, Avenue: 5)
Code: Select all
2 2 2
1 1
2 2
Code: Select all
(Street: 1, Avenue: 1)
Code: Select all
7 7 11
1 2
1 7
2 2
2 3
2 5
3 4
4 2
4 5
4 6
5 3
6 5
Code: Select all
(Street: 3, Avenue: 4)
The problem is in multiple input format. So, your sets will be like
Input:
Output:
And your first case is also wrong.
Input:
Code: Select all
4
22 22 6
1 5
1 4
1 3
2 1
3 10
3 9
10 10 1
5 5
2 2 2
1 1
2 2
7 7 11
1 2
1 7
2 2
2 3
2 5
3 4
4 2
4 5
4 6
5 3
6 5
Code: Select all
(Street: 1, Avenue: 4)
(Street: 5, Avenue: 5)
(Street: 1, Avenue: 1)
(Street: 3, Avenue: 4)
Ami ekhono shopno dekhi...
HomePage
HomePage
i've arranged the multiple input set as u suggested. i used the previous style just to be crystal clear.
now, about the first case: my program sorts it like the following:
why the median shud be (1 4) here?
now, about the first case: my program sorts it like the following:
Code: Select all
1 3
1 4
1 5
2 1
3 9
3 10
If all the friends meet at (1, 4)
If all the friends meet at (1, 5)
So, they both are optimal ones. But the problem states
And if you are following my algorithm (as I described before) then I think that you haven't understood it correctly.
Code: Select all
1 3 => 0 + 1 = 1
1 4 => 0 + 0 = 0
1 5 => 0 + 1 = 1
2 1 => 1 + 3 = 4
3 9 => 2 + 5 = 7
3 10 => 2 + 6 = 8
Total Distance => 21
Code: Select all
1 3 => 0 + 2 = 2
1 4 => 0 + 1 = 1
1 5 => 0 + 0 = 0
2 1 => 1 + 4 = 5
3 9 => 2 + 4 = 6
3 10 => 2 + 5 = 7
Total Distance => 21
(1, 4) is smaller than (1, 5). So, the output should be (1, 4).If there is more than one candidate point, the rule imposes that the meeting point is the one corresponding to the smaller number for street and avenue.
And if you are following my algorithm (as I described before) then I think that you haven't understood it correctly.
Ami ekhono shopno dekhi...
HomePage
HomePage
After sorting you will get
from the above set. . And the median is (1, 4). Hope you understand my algorithm.
Code: Select all
1 1
1 3
1 4
2 5
3 9
3 10
Ami ekhono shopno dekhi...
HomePage
HomePage