ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1255. Graveyard of the Cosa Nostra

Poor tests...
Posted by Korduban [Kiev] 23 Jul 2005 23:38
Look at the function f():

#define SGN(X) (((X)>eps)?1:(((X)<-eps)?-1:0))
const double eps=1e-6;
double sol(double k,double p){
____double l,r,m;
____l=0;
____r=1e5;
____while(r-l>eps){
________m=(l+r)/2;
________if(((k+m)/sqrt(m*m+1))<p)
____________r=m;
________else
____________l=m;
____}
____return m;
}
int f(double k,double p){
____int n;
____double x,w;
____if(SGN(p-1)<=0)
________return 0;
____x=sol(k,p);
____w=(1+x*k)/sqrt(x*x+1);
____if(SGN(p-w)>=0){
________n=floor((p-w)/sqrt(x*x+1));
________return(1+(int)n);
____}else
________return 0;
}

My (like any other) AC program outputs "0" for test "99 100", but it's incorrect! Because we can place coffins near main diagonal.
Let's denote AC-program output as INCORRECT(n,k). Then the correct answer will be

max{INCORRECT(n,k), (n+(n%k))*(n/k)+f(k,n%k)}

and for test "99 100" it will be "82", not "0". Examples:
"5 6" --> "1"
"7 8" --> "2"
"11 12" --> "4"
"9999 10000" --> "9855".
You may cut out respective paper rectangles to check it manually :^). But (it's really fun!) there are no tests like this (i.e. in all cases INCORRECT(n,k) >= (n+(n%k))*(n/k)+f(k,n%k) ), and programs which output INCORRECT(n,k) got AC!
Re: Poor tests...
Posted by Vladimir Yakovlev (USU) 25 Jul 2005 21:18
Coffins must be parallel to cemetery borders.
Problem statement was updated.

Thank you.