Removal of a Sequence (Easy Version)

We start with the sequence

$1,2,3,\dots,10^{12}.$

Each operation deletes the elements currently sitting at positions

$y, 2y, 3y, \dots$

Then the sequence closes up and positions are renumbered. We need the value at final position $k$ after doing this $x$ times.

The annoying part is that deletions are based on current positions, not original values. So trying to track which original numbers get deleted forward is a mess. Classic trap. Don't step in it.

Go backwards instead.

Suppose after one deletion round, an element is at position $p$. What was its position before that deletion round?

During one operation, every $y$-th old position is deleted. So among every block of $y$ old positions, only $y-1$ survive:

$1,2,\dots,y-1 \quad \text{survive, and } y \text{ dies}.$

That means the survivor positions after deletion correspond to old positions like this:

$1,2,\dots,y-1,y+1,y+2,\dots,2y-1,2y+1,\dots$

So the $p$-th survivor has skipped one deleted old position for every full group of $y-1$ survivors before it.

Therefore, for $y>1$:

$$old(p)=p+\left\lfloor\frac{p-1}{y-1}\right\rfloor.$$

That's the whole trick. Tiny formula, big vibes.

Now if the final $k$-th element exists, we can reverse all $x$ operations:

$$pos = k$$

and repeat $x$ times:

$$pos \leftarrow pos + \left\lfloor\frac{pos-1}{y-1}\right\rfloor.$$

After reversing all operations, pos is the original position of the final $k$-th survivor. Since the original sequence is literally

$1,2,3,\dots,10^{12},$

that original position is also the answer value.

If at any point pos > 10^{12}, then this supposed survivor would need to come from outside the original sequence. In normal human terms: the resulting sequence has fewer than $k$ elements. Output $-1$.

There is one special case: $y=1$.

Then the operation removes positions

$1,2,3,\dots,n,$

so the whole sequence gets nuked on the first operation. Since $x \ge 1$, the answer is always $-1$.

Why checking pos > 10^{12} works

The inverse map tells us the minimum original position needed for the final position $k$ to exist after a certain number of remaining reverse steps. If that original position exceeds $10^{12}$, then the finite starting sequence simply was not long enough. No extra length simulation is needed.

Complexity

We do exactly $x$ iterations per test case.

$O(x)$

Since this is the easy version and $x \le 10^5$, with at most $10$ tests, this is easily fine. The computer will survive. Probably.