I use formula, i use binary search, i use linear search, and always got WA#8.
search
cin>>x>>y>>n;
double X=(int)((x+0.05)*n);
double Y=y+0.05;
while (X/n>=x+0.05) X--;
int ans=0;
while  (((double)(ans+X)/(ans+n))>=y+0.05 )ans++;
cout<<ans;
i'm going crazy: why it's not work??

Edited by author 08.10.2006 00:50

what if n==1?

Ha-ha!
I've solved it!!!!

I think that you don't need to use binary search because of your formula is almost right, but it's ALMOST...

I've had WA #8 too.. and I find out that's wrong in my solution in this test. I use only mathematic formulas.

If you buy me beer in Rybinsk I told you what's wrong... But now... ;) i'm waitin' for some beer...

I buy you beer in any case in Rybinsk. Give me test case where are i'm wrong.

If x=10.0 then we shouldn't increase it right?

Ivan, I think that Georgy Kerensky is right!
when x is 10.0 then your double X must be equal to (int)(x*n) because of there is simple average 10.05 can't be!

Also, I think that this inequality [ (ans+X)/(ans+n))>=y+0.05 ] you must solve in integer numbers...
When I write in this way I'd got WA in different tests. But when this condition became to integer comparison I've got Accepted program...

Here some test cases for testing your decision:
10 1 1000000 -> 179000001
10 1 1 -> 180 (not 179!)
10 7.7 123456 -> 41153

also try to testing your program in different tests from this forume...

i've got AC!!! all problem in small bug whith precision. We cannot use :
while  (((ans+X)/(ans+n))>=y+0.05 )ans++;
but we can use:
while  (((ans+X)/(ans+n))>=y+0.0499999999999 )ans++;
and
if (x!=10.0){
    X=(int)((x+0.05)*n);
    while (X/n>=x+0.049999999999) X--;
    }
    else
    {
        X=x*n;
    }

Thanks man! At last I got AC. I just rewrited the same idea by searching X in your terms, 'cause I am writing in pascal and this ancient tool doesn't know how to use Trunc or division:( unfortunately, for example while division instead of 179.00000 it gets 178.999898989 and so on with such things and in watch writes 179, and trunc gives 178 so it is very very interesting:)
 alright thanks friends again

Maxim, thank you for you tests! :)

To all:
The problem can be solved without any search and without  any floating-point arithmetics (but with int64 for safety). Just use these geneal rules for integer fractions:

b>0:
floor(a/b) = a>=0 ? a/b : -ceil(-a,b)
ceil(a/b) = a>=0 ? (a+b-1)/b : -floor(-a, b)

a>=0, b>0:
round(a/b) = a/b + ((a%b)*2>=b ? 1 : 0)

here / is integer division. % is remainder. X?A:B evaluates to 'A' if 'X' is true, evaluates to 'B' otherwise

max x: x <= a/b ------> x = floor(a/b)
max x: x <  a/b ------> x = floor((a-1)/b)
min x: x >= a/b ------> x = ceil(a/b)
min x: x >  a/b ------> x = ceil((a+1)/b)

E.g. to find maximal initial nominator in general case we have to solve the inequality: A/N < (X*100+5)/100, A->MAX

Edited by author 26.08.2008 16:48