OJ Board

Posted: **Fri Jan 09, 2004 8:45 pm**

Can anyone think of any weird input/output for this problem? As far as I can tell, it's a pretty straight forward counting problem, but I keep getting WA...

Posted: **Sat Jan 17, 2004 12:47 pm**

As always when dealing with floats/reals two things are important:
- precision (what datatype to use);
- comparison (equality of two numbers is defined within a margin of error).
Think about that. I only got AC on my third attempt...

Posted: **Sun Jan 18, 2004 12:11 pm**

Actually the problem was because the data set used to test was wrong... they fixed it and now I've got AC'ed. :p Forgot to delete the post though...

Thanks for your help anyway.

Posted: **Tue Feb 10, 2004 7:29 pm**

What's the correct data set for this problem . ??
I have another question ,can the i comlumn of the gravity be m and or j column be n?

Posted: **Wed Feb 11, 2004 12:18 am**

zizi wrote:What's the correct data set for this problem . ??
I have another question ,can the i comlumn of the gravity be m and or j column be n?

I think the gravity column can be any of the valid columns.

Posted: **Thu Aug 04, 2005 9:50 pm**

Could somebody post some test cases ?
Are there any critical cases ?

I think I have no precision problems ( see the post from little joey )
and I always print the largest values of column and row in cases when
there is more than one gravity point.
But I keep getting WA.

Currently I can not find out where my BUG is.
Any help is welcome.

Posted: **Thu Aug 04, 2005 9:59 pm**

Could someone with an ACC program give me the answers
for the following input ( see below ):

INPUT

Code: Select all

5 5
0.1 0.2 0.1 0.2 0.1
0.1 0.2 0.3 0.1 0.1
0.2 0.3 0.1 0.1 0.3
0.4 0.1 0.1 0.1 0.2
0.2 0.2 0.3 0.3 0.1

5 10
0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1
0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2
0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3
0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4
0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.6

3 3 
0.0 0.0 0.0
0.0 0.0 0.0
0.0 0.0 0.0

1 1
0.5 

5 5
0.1 0.1 0.1 0.1 0.9 
0.2 0.2 0.2 0.2 0.9 
0.3 0.7 0.3 0.9 0.9 
0.4 0.4 0.4 0.9 0.9 
0.5 0.5 0.5 0.5 0.9

5 5
0.1 0.1 0.1 0.1 0.9 
0.2 0.2 0.2 0.2 0.9 
0.3 0.11 0.3 0.9 0.9 
0.4 0.44 0.4 0.9 0.9 
0.5 0.15 0.25 0.5 0.9

5 5
0.1 0.1 0.1 0.1 0.3 
0.2 0.2 0.0002 0.2 0.2 
0.3 0.12 0.3 0.9 0.1 
0.4 0.4 0.4 0.9 0.9 
0.5 0.5 0.5 0.5 0.9

5 5
0.1 0.1 0.1 0.1 0.6 
0.2 0.2 0.2 0.2 0.004 
0.3 0.7 0.3 0.2 0.1 
0.4 0.4 0.4 0.9 0.1 
0.5 0.5 0.5 0.5 0.1

5 5
0.1 0.1 0.1 0.1 0.9 
0.2 0.2 0.2 0.3 0.9 
0.3 0.17 0.3 0.4 0.9 
0.4 0.14 0.4 0.1 0.9 
0.5 0.5 0.15 0.5 0.99

10 10
0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1  
0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 
0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 
0.1 0.1 0.1 0.2 0.1 0.1 0.1 0.1 0.1 0.1 
0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 
0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1  
0.77 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.99 0.1 
0.1 0.88 0.1 0.1 0.77 0.1 0.1 0.1 0.1 0.1 
0.1 0.1 0.66 0.1 0.17 0.1 0.1 0.9 0.1 0.00001 
0.1 0.1 0.1 0.90 0.880 0.1 0.1 0.99 0.00001 0.222 

0 0

My WA program prints:

OUTPUT

Code: Select all

Case 1: center at (3, 3)
Case 2: center at (4, 6)
Case 3: center at (3, 3)
Case 4: center at (1, 1)
Case 5: center at (3, 4)
Case 6: center at (3, 4)
Case 7: center at (4, 4)
Case 8: center at (4, 3)
Case 9: center at (3, 4)
Case 10: center at (7, 5)

Thanks in advance.

Posted: **Thu Aug 04, 2005 10:11 pm**

Your output is correct.

Posted: **Thu Aug 04, 2005 11:01 pm**

So my problem should be some stupid one...
Some boundary case or special chars in input ...
Who knows...

Actually this is worse as it is harder to fix.

Maybe I still have some logical BUG ?!

Posted: **Fri Aug 05, 2005 12:43 pm**

I rewrote my program in Java ( previously it was in C++ ) and
I made it more defensive with respect to input. And I got ACC.

Still I do not know why the C++ program gets WA and not ACC.

I mean I use only scanf () and not gets () which makes my program
automatically skip blank lines and so on. This way it also
DOES NOT assume that the format of a test case is :

cntRows(N) cntCols(M)
..................line 1 ( having M double numbers on it )
..................line 2 ( having M double numbers on it )
..................
..................line N ( having M double numbers on it )
<blank line>

So, despite the fact that my C++ program does not rely on
exactly such format of an input block ( test case ) it gets WA.
And I am sure the problem of my C++ program was somehow
input related.

I can see there're very few submissions for this problem and
there're also very few ACC programs. Is this due to I/O stuff ?
I mean, it is an easy problem with only about 150 ACC programs.

Posted: **Sat Mar 25, 2006 10:27 am**

The main reason for the low number of submissions is because this is a world finals problem and it is in volume 2.

I used C++ and have no problems with input/output.

Posted: **Sun Mar 25, 2007 1:58 pm**

I change variables' type from double to long double. And also calculate the difference from right to left, from bottom to top. My code is written in C++. It works well.

Posted: **Fri Jun 22, 2007 6:41 am**

Hi, I think this problem is straightforward, but it gives me multiple WA..., can anyone give me some hints? I'm very very curious bout this problem...
Thanks

Code: Select all

#include<stdlib.h>
#include<stdio.h>
#define MAX 26
#define INF 1000000000000

long double arr[MAX][MAX];
int Row,Col;
int ansR,ansC;
long double smallRow,smallCol;

void compute(int r,int c){
   long double tempA,tempB,res,res2;
   int i,j;
   tempA=tempB=0;
   for(i=r-1;i>=0;i--)
	  for(j=0;j<Col;j++) tempA+=arr[i][j];
   for(i=r+1;i<Row;i++)
	  for(j=0;j<Col;j++) tempB+=arr[i][j];
   if(tempA>tempB) res=tempA-tempB;
   else res=tempB-tempA;
   tempA=tempB=0;
   for(i=0;i<Row;i++)
	  for(j=c-1;j>=0;j--) tempA+=arr[i][j];
   for(i=0;i<Row;i++)
	  for(j=c+1;j<Col;j++) tempB+=arr[i][j];
   if(tempA>tempB) res2=tempA-tempB;
   else res2=tempB-tempA;
   if(res2<=smallCol&&res<=smallRow)   {smallRow=res;smallCol=res2;ansR=r;ansC=c;}
}

void main(){
   int r,c;
   int i,j,no=0;
   long double temp;
   
   while(scanf("%d %d",&Row,&Col)==2)
   {
	  if(!Row&&!Col) break;
	  ++no;
	  smallRow=smallCol=INF;
	  for(i=0;i<Row;i++)
		 for(j=0;j<Col;j++)
		 {
			scanf("%Lf",&temp);
			arr[i][j]=temp;
		 }
	  for(i=0;i<Row;i++)
		 for(j=0;j<Col;j++)
			compute(i,j);
	  printf("Case %d: center at (%d, %d)\n",no,ansR+1,ansC+1);
   }
}

Posted: **Fri Jun 22, 2007 6:58 am**

algoJo wrote:Hi, I think this problem is straightforward, but it gives me multiple WA..., can anyone give me some hints? I'm very very curious bout this problem...
Thanks
Code: Select all
   ...
   if(res2<=smallCol&&res<=smallRow)   {smallRow=res;smallCol=res2;ansR=r;ansC=c;}
   ...

Hmm.. I'm not sure if your WAs are caused by precision error..
But, when I compare 2 floating point numbers, I had to use EPS to get AC..
My data type is "double" and EPS value is 1e-6

Posted: **Fri Jun 22, 2007 7:10 am**

Thanks for replying helloneo..

I still got WA

this is how I implement the EPS

Code: Select all

if(res2+1e-6<=smallCol+1e-6&&res+1e-6<=smallRow+1e-6)   {smallRow=res;smallCol=res2;ansR=r;ansC=c;}

is it rite?
hmm...., is there any tricky input on this problem...

OJ Board

250 - Pattern Matching Prelims

250 - Pattern Matching Prelims

Why it always get WA...

Re: Why it always get WA...