From the Unknown (Hard Version)

This is interactive, so the real goal is not to compute from input. The goal is to design at most two articles whose returned line counts force the value of $W$.

Equal Words

Suppose we query an article with $N$ copies of one word length $B$.

If $W<B$, the editor cannot display the article, so the answer is $0$.

Otherwise, one line can contain exactly

$$q=\left\lfloor\frac WB\right\rfloor$$

words, so the answer is

$$r=\left\lceil\frac Nq\right\rceil =\left\lceil\frac{N}{\left\lfloor W/B\right\rfloor}\right\rceil.$$

For a fixed nonzero answer $r$, the possible values of $q$ form an interval:

$$q\in\left[\left\lceil\frac Nr\right\rceil,\left\lfloor\frac{N-1}{r-1}\right\rfloor\right].$$

Using integer division:

$$q_{\min}=\left\lfloor\frac{N-1}{r}\right\rfloor+1, \qquad q_{\max}=\left\lfloor\frac{N-1}{r-1}\right\rfloor.$$

Since $q=\lfloor W/B\rfloor$, this gives

$$L=q_{\min}B, \qquad R=(q_{\max}+1)B-1.$$

Also cap $R$ by $10^5$.

A key fact: this interval is shaped nicely. In the $q$-interval, we have $2q_{\min}>q_{\max}$. If not, then $2q_{\min}$ would still be inside the interval, but

$$\left\lceil\frac{N}{2q_{\min}}\right\rceil<r,$$

contradiction. After scaling, this gives enough room to isolate the second query.

Resolving An Interval

Now assume we know $W\in[L,R]$. Let

$$S=L+1.$$

If $W=L$, then a word of length $S$ is too large, so any query containing $S$ returns $0$. That handles the left endpoint cleanly.

For every threshold

$$i=L+2,L+3,\ldots,R,$$

put this pair into the second article:

$$(S,\ i-S).$$

The pair sum is exactly $i$, so it fits on one line exactly when $i\le W$.

The pairs do not interfere with each other. Because $2S>R\ge W$, after a fitting pair, the next $S$ cannot join the same line. If a pair does not fit, then its second word plus the next $S$ has sum $i>W$, so that also cannot join. Good: each pair acts independently instead of turning into wrapping soup.

Let

$$m=R-L-1$$

be the number of pairs, and let the second answer be $r_2$.

If $r_2=0$, then $W=L$.

Otherwise, the number of fitting pairs is

$$W-(L+1).$$

Each fitting pair uses $1$ line, and each non-fitting pair uses $2$ lines, so

$$r_2=2m-(W-L-1).$$

Therefore

$$W=L+1+(2m-r_2).$$

The implementation uses the article length itself, $2m$, in that formula.

The Low Case $W<B$

If the first query returns $0$, then $W<B$.

Use the second query as $B^2$ copies of $1$. The answer is

$$r=\left\lceil\frac{B^2}{W}\right\rceil.$$

For $1\le W<B$, these answers are all distinct, because for consecutive values:

$$\frac{B^2}{W}-\frac{B^2}{W+1} =\frac{B^2}{W(W+1)}>1.$$

So the ceilings strictly decrease. We recover

$$W=\left\lfloor\frac{B^2-1}{r-1}\right\rfloor.$$

Constants

We need the total queried article length to be at most $25000$.

A working brute-forced choice is

$$B=116,\qquad N=11343.$$

Then:

• first query length is $11343$;
• if $W<B$, second query length is $116^2=13456$;
• otherwise, the largest possible interval length is at most $6263$, so the pair query length is at most $2\cdot6263$.

Thus the worst case is

$$11343+13456=24799\le25000.$$

The manual hack format is for the interactor/test data. The contestant program still follows the interactive protocol: print queries, flush, read answers, and finally print ! W.