Overview

This problem asks you to calculate “how much each smartphone’s battery decreases in total over \(K\) days” all at once, and count the number of devices that still have \(1\%\) or more remaining after \(K\) days.

Analysis

The key observation is that “for the \(K\) days until the charger arrives, the battery decreases by a fixed amount \(D\%\) each day.”
Therefore, the battery remaining after \(K\) days can be computed in one shot for each device:

• Decrease: \(D \times K\)
• Remaining: \(W_i - D \times K\)

A naive approach of “simulating day by day for \(K\) iterations, decreasing each time” would result in \(O(NK)\) time complexity. Given the constraint \(K \le 10^9\), this would not finish in a realistic amount of time (it would result in TLE).

Instead, we compute the total decrease over \(K\) days all at once as \(D \times K\), and simply check the condition for each \(W_i\).

Also, according to the problem statement, a device is usable if it has “\(1\%\) or more after \(K\) days,” so the condition is: - \(W_i - D \times K \ge 1\) (\(0\) is not acceptable).

Example: If \(D=3, K=4, W_i=15\), then the decrease is \(12\), the remaining is \(3\), so the device survives.

Algorithm

1. Read \(N, D, K\) and the array \(W\) from input.
2. Compute \(dec = D \times K\) (total decrease over \(K\) days).
3. Count the number of elements \(w \in W\) satisfying \(w - dec \ge 1\).
4. Output that count.

Complexity

• Time complexity: \(O(N)\) (just checking each smartphone once)
• Space complexity: \(O(N)\) (to store the input array)

Implementation Notes

• Since \(K\) can be very large, do not simulate by looping over each day (compute \(D \times K\) all at once).

• The condition is “at least \(1\),” so the check is \(w - dec \ge 1\) (equivalent to \(> 0\)).

• In Python, integers have arbitrary precision, so there is no need to worry about overflow even if \(D \times K\) is large.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, D, K = map(int, input().split())
    W = list(map(int, input().split()))
    dec = D * K
    ans = sum(1 for w in W if w - dec >= 1)
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.