Rating:
# BlindCoder writeup (En)
## Problem
There are a group $S$ of unknown integers $n$ such that $0 \le n < 2^{32}=4294967296$with size $50$.
By sending formula $f$, which consists of logical operations and arithmetric operations, we can get the count of the result $x\in S$ which returned $f(x)$ that equals to the least significant digit of$x$.
We can send arbitrary $f$ as much as we like until $1000$ times. Determine $S$.
Example:
When $S=\{0,1,\ldots,49\}$, if we send $f(x)=0$ it rturns $5\ (x=0,10,20,30,40)$
## Examination
The least significant digit of $x$ is $x\,\%\,10$ and $-1$ cannot be the digit. Then, on the logical function $P(x)$ if we let $f$ be
$f(x)=P(x)\,?\,(x\,\%\,10)\,:\,-1$
then we'll get "the number of $S$ which satisfies $P(x)$"
## Step 1
First, turn the information "there's $50$ numbers in $[0,2^{32})$" into 50 pieces of informations "there's $1$ number in $[a,b)$", where every $[a,b)$ does not fall on each other.
This can be accomplished by choosing the interval $[a,b)$ that contains the multiple element of $S$ and querying the count of elements in $\left[a,\dfrac{a+b}{2}\right)$, and repeat them.
By using this method, we can obtain 50 individual intervals that doesn't fall on each other with about $71$ queries.
## Step 2
Now we narrow the interval obtained in step 1 to one point.
For simplicity, let $\dfrac{2^{32}}{64}=2^{26}$ be the length of the interval obtained in step 1.
### Strategy A
The length of the interval can be halved by asking "the number of pieces in $[a,b)$" for interval $\left[a,\dfrac{a+b}{2}\right)$.
So it seems like this problem can be solved by repeating this until the length of all the intervals is 1... but the query required will be $26\times50=1300$ times, which is not enough time.
### Strategy B
Consider sending a query to two intervals at the same time.
For intervals $[a,b)$ and $[c,d)$, if you ask "the number of pieces in $\left[a,\dfrac{a+b}{2}\right)$ or $\left[c,\dfrac{c+d}{2}\right)$", you will get 0, 1 or 2.
If you got 0 or 2, both intervals can be halved. In other words, the effect is equivalent to two queries of strategy A.
If you got 1, you can either be included in $\left[a,\dfrac{a+b}{2}\right)$ or $\left[c,\dfrac{c+d}{2}\right)$. If you can cut one in half, you can cut the other in half.
In other words, it's as effective as one query of strategy A.
From the above, one query can be expected to be enough for 1.5 queries in Strategy A (in fact, it is slightly less, e.g., when there is only one interval left).
Thus, the number of queries needed is $1300/1.5=866.66\ldots$, which is enough time even when combined with $71$ queries in step 1.
