Overview

This problem asks you to process \(N\) tasks in order, choosing between energy-saving mode (processing power \(A\), no battery consumption) and full-power mode (processing power = current battery level, battery halved after use). You must determine whether all tasks can be completed, and if so, minimize the number of times full-power mode is used.

Analysis

Key Insight

For each task \(i\), considering processing power:

• If \(H_i \leq A\): Energy-saving mode is sufficient. Since it doesn’t consume battery, there is no reason to use full-power mode.
• If \(H_i > A\): Energy-saving mode lacks sufficient processing power, so full-power mode must be used.

In other words, the tasks that require full-power mode are uniquely determined. The optimal strategy is to “use it only when you must.”

Why Using Full-Power Mode Unnecessarily is Detrimental

Using full-power mode halves the battery. This reduces the processing power available for future full-power mode uses, so using it unnecessarily is harmful. When energy-saving mode suffices, it should be used instead.

Algorithm

We solve this with a greedy approach.

1. Initialize the battery level to \(M\) and process tasks from the beginning in order.
2. If \(H_i \leq A\), use energy-saving mode; the battery remains unchanged.
3. If \(H_i > A\), full-power mode must be used:
   • If the current battery level \(p\) is less than \(H_i\), the task cannot be completed, so output -1 and terminate.
   • If \(p \geq H_i\), use full-power mode, increment the count by \(1\), and update the battery to \(\lfloor p/2 \rfloor\).
4. If all tasks are successfully processed, output the count.

Concrete Example

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

Task	\(H_i\)	Mode	Battery (before → after)
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 examined exactly once
• Space complexity: \(O(N)\) — for storing the array \(H\)

Implementation Notes

• Since \(M\) and \(H_i\) can be up to \(10^{18}\), long long type must be used.

• Battery halving uses integer division battery / 2, which automatically truncates in C++.

• Since the task order is fixed, a simple front-to-back simulation is sufficient. The decisions are local (only comparing the current \(H_i\) with \(A\) and with the current battery), so no search or binary search is needed.

  Source Code

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    long long N, M, A;
    cin >> N >> M >> A;
    
    vector<long long> H(N);
    for (int i = 0; i < N; i++) cin >> H[i];
    
    long long battery = M;
    long long count = 0;
    
    for (int i = 0; i < N; i++) {
        if (H[i] <= A) {
            // Use energy-saving mode, no battery cost
            continue;
        } else {
            // Must use full-power mode
            if (battery < H[i]) {
                cout << -1 << endl;
                return 0;
            }
            count++;
            battery = battery / 2;
        }
    }
    
    cout << count << endl;
    return 0;
}

---

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