When I'm taking part in Educational Codeforces Round 87,I come up with a random solution.

But I didn't think it can pass.(In fact I'm wrong and the solution has more than 99.99% possibility to pass)

And I think for a long time to find a non-random solution without getting good ideas

Can somebody solve this problem?

Here is my random solution 80523216 You can easily prove that it has a high possibility to pass.

I wrote my random solution here. I think the solution is similar to you :)

If we can find

anystone box (not necessarily minimum index) in at most $$$29$$$ queries, we can solve this problem. This seems much easier than the original problem.If we solve this sub-problem deterministically, we can solve the original problem deterministically. Though, I haven't come up with the solution yet.

(I expect that the intended solution is also randomized. That's because hacks are prohibited for this problem.)

Yes you are right... I am also trying to solve this,but got no ideas. So I think other ways may work instead of this.

My solution is not randomized (link: https://codeforces.com/contest/1354/submission/80509851)

Basically, I try to find a stone by splitting the objects into two groups (if it's odd, leave one out to check for later). Then, the stone is likely to be in the heavier group.

However, someone pointed out that there are testcases that could break my solution, like

`100 97 99 99 100 100 100 1`

, where 100 is a stone. If I split by ranges, it will take the first 4 (100 97 99 99), but will then go to (99 99) as it is heavier than (100 97).Quite sure the solution is very likely to pass (because k <= n/2). But in hindsight, I probably should have randomized the indexes of the objects.

Nice solution.But it is still not correct.