Overview

This problem can be solved using a Greedy approach, where at each step we make the optimal choice of whether to process each task in “energy-saving mode” or “full-power mode.”

Analysis

The key insight of this problem is that “keeping as much battery remaining as possible is always advantageous for future tasks.”

The battery level \(p\) starts at an initial value of \(M\) and decreases to \(\lfloor p/2 \rfloor\) each time full-power mode is used. Once the battery decreases, it never recovers. Therefore, in situations where battery consumption can be avoided, conserving it is always the best strategy.

For each task \(i\) (with required processing power \(H_i\)), let’s consider how to choose the mode step by step, given the current battery level \(p\).

1. When the task can be cleared in energy-saving mode (\(H_i \le A\))

If the processing power \(A\) of energy-saving mode alone is sufficient to complete the task, energy-saving mode should always be chosen. Full-power mode could also complete the task, but the battery level would be halved, only putting us at a disadvantage for subsequent tasks. There is absolutely no benefit.

2. When the task cannot be cleared in energy-saving mode (\(H_i > A\))

Since energy-saving mode lacks sufficient processing power, full-power mode must be chosen. In this case, there are two further situations: - When \(p \ge H_i\): The task can be completed in full-power mode. The battery level \(p\) decreases to \(\lfloor p/2 \rfloor\), and the full-power mode usage count increases by \(1\). - When \(p < H_i\): With the current battery level, even full-power mode doesn’t provide enough processing power. Even if we had consumed less battery earlier by conserving it, there is no way to increase the battery, so it is impossible to clear this task regardless of what we do. Therefore, we output -1 and terminate at this point.

In this way, by simply making the choice “use energy-saving mode if possible, otherwise use full-power mode (or declare it impossible)” sequentially from the first task, the optimal procedure (minimizing the number of full-power mode uses) is automatically determined.

Concrete Example

For \(N=3, M=10, A=5\), with required processing powers \(H = [4, 8, 3]\):

1. First task (\(H_1 = 4\)): \(H_1 \le A\) (\(4 \le 5\)), so we choose energy-saving mode. Battery remains \(p = 10\).
2. Second task (\(H_2 = 8\)): \(H_2 > A\) (\(8 > 5\)), so we choose full-power mode. \(p \ge H_2\) (\(10 \ge 8\)) so it can be cleared. Battery becomes \(p = \lfloor 10/2 \rfloor = 5\), and the usage count becomes \(1\).
3. Third task (\(H_3 = 3\)): \(H_3 \le A\) (\(3 \le 5\)), so we choose energy-saving mode. Battery remains \(p = 5\).

All tasks are completed, and the minimum number of full-power mode uses is 1.

Algorithm

1. Initialize a variable \(p\) representing the battery level to \(M\), and a variable \(ans\) representing the number of full-power mode uses to \(0\).
2. For \(i = 1, 2, \ldots, N\), perform the following operations in order:
   • If \(H_i > A\):
     • If \(p < H_i\), clearing is impossible, so output -1 and terminate immediately.
     • Otherwise, use full-power mode. Update \(p \leftarrow \lfloor p / 2 \rfloor\) and increment \(ans\) by \(1\).
   • If \(H_i \le A\):
     • Use energy-saving mode. Neither \(p\) nor \(ans\) changes.
3. After successfully processing all tasks, output the final value of \(ans\).

Complexity

• Time Complexity: \(O(N)\) We only scan through the array of tasks once from front to back. The decision and battery update for each task can be done in \(O(1)\) constant time, so the overall complexity is proportional to \(N\). This runs sufficiently fast for the constraint \(N \le 3 \times 10^5\).
• Space Complexity: \(O(N)\) This is the memory required to store the required processing powers \(H\) of the input tasks in an array (list).

Implementation Notes

• Integer types (notes for other languages): The input values \(M, A, H_i\) can be as large as \(10^{18}\), which are very large values. In Python, arbitrary-precision integers are handled automatically so there is no concern about overflow, but when using languages like C++, you need to use 64-bit integer types (such as long long).

• Fast I/O: When handling input of scale \(N = 3 \times 10^5\) in Python, naively repeating input() may not fit within the time limit (TL). By using sys.stdin.read().split() to read all input at once, you can eliminate the I/O bottleneck.

  Source Code

import sys


def main():
    # 入力を一度に読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    M = int(input_data[1])
    A = int(input_data[2])

    p = M
    ans = 0

    # 各タスクの処理
    for i in range(N):
        h = int(input_data[3 + i])
        if h > A:
            if p < h:
                print(-1)
                return
            p //= 2
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

---

This editorial was generated by gemini-3.5-flash-thinking.