|
|
back to boardPoor tests... 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... Coffins must be parallel to cemetery borders. Problem statement was updated. Thank you. |
|
|