Overview

When processing \(N\) tasks in order, you are forced to use full power mode only for tasks where energy-saving mode lacks sufficient processing capability. The problem asks you to count the number of times full power mode is used while determining whether the battery is sufficient.

Analysis

Key Observations

1. Tasks that can be processed in energy-saving mode (\(H_i \leq A\)): There is no need to use full power mode. Since full power mode halves the battery, you should conserve battery for the future.

2. Tasks that cannot be processed in energy-saving mode (\(H_i > A\)): You have no choice but to use full power mode. At this point, if the current battery level \(p\) is less than \(H_i\), the task cannot be completed.

Correctness of the Greedy Approach

To minimize the number of times full power mode is used, the optimal strategy is to “use full power mode only for tasks where it is unavoidable.” The reasoning is as follows:

• Using full power mode on tasks where \(H_i \leq A\) will complete the task but wastes battery unnecessarily.
• For tasks where \(H_i > A\), energy-saving mode lacks sufficient processing capability, so full power mode must always be used.

Therefore, “the number of times full power mode is used” equals the number of tasks where \(H_i > A\), and we only need to verify whether this is achievable.

Algorithm

1. Examine tasks in order from the \(1\)st task onward.
2. If \(H_i \leq A\), use energy-saving mode. The battery does not change.
3. If \(H_i > A\), full power mode must be used:
   • If the current battery level is less than \(H_i\), the task cannot be completed, so output -1 and terminate.
   • Otherwise, use full power mode, update the battery to \(\lfloor \text{battery} / 2 \rfloor\), and increment the count by \(1\).
4. If all tasks can be processed, output the count (number of times full power mode was used).

Concrete Example

For \(N=3,\ M=10,\ A=3,\ H=[2, 8, 4]\):

Task	\(H_i\)	Mode	Battery (before → after)	Result
1	2	Energy-saving (\(2 \leq 3\))	\(10 \to 10\)	○
2	8	Full power (\(8 > 3\))	\(10 \geq 8\), \(10 \to 5\)	○
3	4	Full power (\(4 > 3\))	\(5 \geq 4\), \(5 \to 2\)	○

Answer: 2

Complexity

• Time complexity: \(O(N)\) — each task is checked exactly once
• Space complexity: \(O(N)\) — for storing the array \(H\)

Implementation Notes

• Battery halving can be implemented with battery >> 1 (right bit shift). This is equivalent to \(\lfloor \text{battery} / 2 \rfloor\).

• Although \(M\) and \(H_i\) can be as large as \(10^{18}\), Python handles arbitrary-precision integers, so there is no concern about overflow.

• Since the battery is halved each time full power mode is used, full power mode can be used at most about \(60\) times (\(\log_2(10^{18}) \approx 60\)). If there are more tasks with \(H_i > A\) than that, the battery will reach \(0\) and completion becomes impossible.

  Source Code

import sys
input = sys.stdin.readline

def main():
    N, M, A = map(int, input().split())
    H = list(map(int, input().split()))
    
    battery = M
    count = 0
    
    for i in range(N):
        if H[i] > A:
            if battery < H[i]:
                print(-1)
                return
            count += 1
            battery = battery >> 1
    
    print(count)

main()

---

This editorial was generated by claude4.6opus-thinking.