Help in REALBIN

In the question, it is mentioned that divyam can add Y or subtract Y and it has not been mentioned that divyam doesn’t know what X is.
I tried to check whether the decimal is terminating or non terminating for which I got TLE as the numbers are up to 10^18. The solution given in the editorial will fail for 1/10 or 1/5.
Divyam can either add or subtract so if the number is say 0.2 then he can add some Y to make it 1 but that same Y, if subtracted, will make it negative which can not happen.
But in the question, it is given that he can perform either addition or subtraction. The question does not mention that divyam doesn’t know the number. if it had been mentioned then we can say that the answer given is true.

Please correct me if I am wrong.
It would be great if anyone could help me out.

Thank you

The initial value of X must satisfy 0 < X < 1, but I don’t think subsequent values of X are constrained this way.

You can assume that Divyam always knows the current value of X and the value Y that Chef has chosen.

2 Likes

well, the whole idea is to arrive at a point where no matter what divyam does add or subtract chef will win. for example, if the number is 0.5 (or 1/2 ) and the chef also gives 0.5 (or 1/2 ), if divyam adds these two numbers result will be 1 or if subtracted result will be 0. so, we can see in both situations chef can win. another example- let’s say the number is 0.25 (or 1/4 ) and the chef also gives 0.25 (or 1/4 ) now from here u can go to 0 or 0.5 (from here process can go as explained in the previous example). so you can see if the number is like x / (2 ^ y) you can always make result 0 or 1. so basically all you had to do is check if the number B is of form 2 ^ y or not.

Can you please explain why 1/10 or 1/5 are not taken in the solution?

I can’t explain more clearly than the Editorialist has

Can you think of any X which will make it 0 or 1?

I haven’t checked this, but here’s what I think is an explicit strategy for Divyam, for when X={a \over b}; a and b are co-prime; and b is divisible by some prime p\ne2.

Let Y be the number chosen by Chef. I’ll assume Y is rational for the time being. Since p is not equal to 2, I believe it can be shown that at least one of the numerators of X+Y and X - Y is not divisible by p (hint: consider the numerator of X+Y mod p and the numberator of X-Y mod p), so Divyam chooses whichever results in a numerator that is not divisible by p, and so the denominator of the new X, when the fraction is cancelled as far as it can go, is still divisible by p: therefore, if Divyam follows this strategy, we can never end up with X=0 or X=1.

If Y is irrational, Divyam should just set X to either X+Y or X-Y; it doesn’t matter which. X now becomes irrational.

If X is irrational, then if Chef chooses Y as a rational number, both X+Y and X-Y are still irrational, so X remains irrational and so cannot be 0 or 1.

If X is irrational and Chef chooses an irrational number, then I believe it can be shown that at least one of X+Y and X-Y is also irrational, so Divyam should choose whichever leads again to irrational X, which again cannot be 0 or 1.

Try is out with X={1\over10} (p=5)!

1 Like