Recycling Center

The doubling looks annoying, but the key is that a bag’s cost only depends on when it is destroyed.

If bag $i$ is destroyed at second $k$, meaning exactly $k$ doublings have already happened, its weight is

$$a_i \cdot 2^k.$$

It is free iff

$$a_i \cdot 2^k \le c.$$

Remember the statement says you pay only when the weight is strictly greater than $c$, so weight exactly $c$ is still free. Tiny detail, easy place to throw away a WA like a clown.

Turn each bag into a deadline

For every bag, compute the largest $d_i$ such that

$$a_i \cdot 2^{d_i} \le c.$$

That means this bag can be destroyed for free at any time $0,1,\dots,d_i$.

If $a_i > c$, then even destroying it immediately costs $1$, so it has no free deadline and can be ignored when maximizing free destructions.

Since $n \le 30$, we can compute $d_i$ by repeatedly doubling the weight while it stays at most $c$. No floating-point logs needed. Floating point is overkill here and, frankly, a bad habit for integer boundary problems.

Why paid bags can go last

Suppose some schedule destroys a paid bag before a free bag.

Swap those two actions:

• The free bag is now destroyed earlier, so it has been doubled fewer times. If it was free before, it is still free.
• The paid bag is now destroyed later, so it is even heavier. If it cost $1$ before, it still costs $1$.

So the total cost does not increase.

By repeatedly doing this, there is always an optimal schedule where all free destructions happen first, and all paid destructions happen after. Nice. The garbage can wait.

So if we want $m$ bags to be free, we only need to schedule them into times

$$0,1,2,\dots,m-1.$$

Each chosen bag must be placed no later than its deadline.

This is now a classic greedy scheduling problem

We have a bunch of unit-time jobs, each with a deadline $d_i$. We want to schedule as many as possible.

The greedy is:

1. Sort all deadlines increasingly.
2. Let free be the number of free bags already scheduled.
3. For each deadline $d$:
   • If free <= d, schedule this bag at time free and increment free.
   • Otherwise, this bag’s deadline is already too early, so skip it.

Why does this work?

When processing deadlines in increasing order, the current bag is one of the most urgent remaining bags. If the next available free slot is free, then:

• If free <= d, the bag fits, so taking it is always good.
• If free > d, then slots $0$ through $d$ are already filled. There is no earlier slot left for this bag, and replacing a previously chosen bag with this one does not increase the count. So skipping it loses nothing.

At the end, free is the maximum number of bags we can destroy without paying.

Therefore:

$$\text{answer} = n - \text{free}.$$

Complexity

For each test case, we sort at most $n$ deadlines:

$$O(n \log n)$$

with $n \le 30$, so this is comfortably tiny.