Round Trip

We only need to track one number: the smallest rating Vasya can currently have while not sacrificing any rated rounds so far.

Call it $R$.

There are two round types:

• 1: always rated.
• 2: rated only if $R < X$ before the round.

After a rated round, Vasya may choose his new rating anywhere from $R-D$ to $R+D$, clipped at $0$ because rating cannot be negative.

The key observation is brutally simple: lower rating is always at least as good as higher rating.

Why? The only restriction in the future is for div. 2 rounds, and that restriction is:

$$R < X$$

There is never a round that requires Vasya to have rating at least something. So keeping rating high gives no advantage. It only makes future div. 2 rounds harder to enter. That's not strategy, that's self-sabotage with extra steps.

So after every rated round, we should choose the minimum possible next rating:

$$R \leftarrow \max(0, R-D)$$

Now simulate the string.

For a div. 1 round:

It is always rated, so:

$$ans \leftarrow ans + 1$$

and then:

$$R \leftarrow \max(0, R-D)$$

For a div. 2 round:

If $R < X$, it is rated, so count it and drop the rating:

$$ans \leftarrow ans + 1$$ $$R \leftarrow \max(0, R-D)$$

If $R \ge X$, it is unrated. In an unrated round the rating cannot change, so we do nothing.

Why this greedy is correct

We can prove the invariant:

After processing any prefix of rounds, our simulated rating $R$ is the minimum possible rating among all strategies that achieve the maximum possible number of rated rounds in that prefix.

Initially this is true with $R = R_0$.

When the next round is div. 1, every strategy gets this round rated, and choosing the lowest allowed new rating clearly keeps the invariant true.

When the next round is div. 2:

• If our minimum possible $R < X$, then we can make it rated, and again dropping as low as possible is best.
• If our minimum possible $R \ge X$, then every other strategy has rating at least $R$, so every other strategy also has rating $\ge X$. Nobody can make this div. 2 round rated. It must be skipped.

So the greedy never misses a rated round that could have been taken.

Complexity is just one pass over the string:

$$O(n)$$

per test case, with $O(1)$ memory.