Overview

This problem asks us to determine how many of \(N\) smartphones will remain usable after \(K\) days. Each smartphone loses \(D\) percent of battery per day, and we need to count those with at least \(1\) percent remaining after \(K\) days.

Analysis

Key Insight

The most important observation in this problem is that each smartphone can be considered independently.

For the \(i\)-th smartphone: - Current battery level: \(W_i\) percent - Battery level after \(1\) day: \(W_i - D\) percent - Battery level after \(2\) days: \(W_i - 2D\) percent - … - Battery level after \(K\) days: \(W_i - K \times D\) percent

In other words, the battery level after \(K\) days can be calculated with simple subtraction.

Verification with Examples

For example, when \(W_i = 50\), \(D = 10\), \(K = 3\): - Battery level after \(K\) days = \(50 - 10 \times 3 = 20\) percent - Since \(20 \geq 1\), this smartphone remains usable.

On the other hand, when \(W_i = 30\), \(D = 10\), \(K = 5\): - Battery level after \(K\) days = \(30 - 10 \times 5 = -20\) percent - Since \(-20 < 1\), this smartphone has powered off.

About the Naive Approach

Since this problem can be solved with simple calculations, no special techniques are needed. Although \(K\) can be as large as \(10^9\), there is no need to simulate day by day—we can directly calculate the battery level after \(K\) days.

If we were to simulate day by day, the complexity would be \(O(N \times K)\), which would result in TLE since \(K\) can be up to \(10^9\).

Algorithm

1. For each smartphone \(i\), calculate the battery level after \(K\) days
   • Remaining = \(W_i - D \times K\)
2. If the remaining level is \(1\) or more, increment the count
3. Output the final count

Complexity

• Time complexity: \(O(N)\)
  • Because we perform constant-time calculations for each smartphone
• Space complexity: \(O(N)\)
  • Because we store the list of battery levels

Implementation Notes

• Since \(K\) can be as large as \(10^9\), the result of D * K can become very large, but in Python we don’t need to worry about integer overflow.
• The condition is “\(1\) percent or more”, so be careful to include the equality: remaining >= 1.
• Cases where battery level becomes negative are handled correctly (negative values are obviously less than \(1\)).

Source Code

N, D, K = map(int, input().split())
W = list(map(int, input().split()))

count = 0
for w in W:
    # Battery level after K days is W - D * K
    # If this is 1 or more, it's usable
    remaining = w - D * K
    if remaining >= 1:
        count += 1

print(count)

---

This editorial was generated by claude4.5opus.