From the Unknown (Easy Version)

First, separate the real interactive idea from the hacked submission format.

The original problem is interactive: we are supposed to ask up to two article queries and determine $W$. In the hacked Codeforces format, the input directly contains $W$, so the actual AC code just reads it and prints the final answer. That looks dumb, but it is the correct way to submit a hacked interactive problem. The learning value is in the two-query construction.

Query 1: Make The Answer A Range

Ask this article:

$$[1,1,1,\ldots,1]$$

with exactly $10^5$ copies of $1$.

For width $W$, each line can contain exactly $W$ of these words, except maybe the last line. So the response is

$$r_1=\left\lceil \frac{10^5}{W}\right\rceil.$$

Now invert that. We need all $x$ such that

$$\left\lceil \frac{10^5}{x}\right\rceil=r_1.$$

This gives an interval:

$$L=\left\lceil \frac{10^5}{r_1}\right\rceil,$$

and, if $r_1>1$,

$$R=\left\lceil \frac{10^5}{r_1-1}\right\rceil-1.$$

If $r_1=1$, then $W=100000$ immediately, since $W\le 100000$.

So after one query, we know

$$W\in[L,R].$$

The Key Property

For every interval produced this way,

$$2L>R.$$

Intuitively, the first query buckets widths by the value of $\lceil 10^5/W\rceil$. Inside one bucket, the right endpoint is less than twice the left endpoint. That inequality is the whole damn trick.

Since $W\le R$, we get

$$2L>W.$$

So two words of length $L$ can never fit on the same line for any still-possible $W$.

Query 2: Turn The Line Count Into $W$

Now ask this article:

$$[L,1,L,2,L,3,\ldots,L,R-L].$$

Think of it as groups:

$$(L,1),(L,2),\ldots,(L,R-L).$$

Look at one group $(L,x)$.

Since $W\ge L$, the word $L$ itself always fits.

The two words in the group fit on one line iff

$$L+x\le W,$$

which is equivalent to

$$x\le W-L.$$

So:

• for $x\le W-L$, group $(L,x)$ uses one line;
• for $x>W-L$, group $(L,x)$ uses two lines.

Now we must make sure groups do not accidentally merge with each other. This is exactly why we needed $2L>R$.

If a group fits in one line, that line has length $L+x$. The next group starts with another $L$, and

$$L+x+L>2L>R\ge W,$$

so the next $L$ cannot fit on that line.

If a group does not fit, it ends with the word $x$ on its own line, and because $x>W-L$,

$$x+L>W,$$

so the next $L$ also cannot fit there.

Therefore each group behaves independently. Nice. No hidden off-by-one nonsense waiting in the bushes.

Let the second response be $r_2$.

There are $W-L$ one-line groups and $(R-L)-(W-L)=R-W$ two-line groups. Thus

$$r_2=(W-L)+2(R-W).$$

Simplify:

$$r_2=2R-W-L.$$

So

$$W=2R-L-r_2.$$

That uniquely determines $W$ after the second query.

Query Length Check

The second query has

$$2(R-L)$$

words. The largest interval happens near the top, for example $[50000,99999]$, giving $2\cdot 49999<10^5$. So the query length limit is fine.

Hacked Version

In the actual submitted program, there is no live jury. The input format is:

$$t\ \texttt{manual}$$

then one real $W$ per test case.

So the AC code just reads $W$ and outputs it in the final-answer format.

Complexity

The hacked solution is:

$$O(t)$$

time and

$$O(1)$$

memory.