Overview

Given \(N\) smartphones, the problem asks to optimally assign mobile batteries to maximize the number of usable smartphones after \(Y\) hours. We solve this greedily by classifying each smartphone into one of three categories: “already dead,” “survives without charging,” or “dies without charging.”

Analysis

Battery Drain and Power-Off Condition

• Since each smartphone loses \(1\)% battery per hour, the remaining battery after \(Y\) hours is \(A_i - Y\) (%).
• The phone turns off the moment its battery level drops to or below \(L\)%. In other words, the survival condition is that the battery level is strictly greater than \(L\).

Three Categories of Smartphones

Each smartphone can be classified into the following three groups:

1. Already dead (\(A_i \leq L\)): The battery is already at or below \(L\)%, so even connecting a mobile battery won’t revive it. It cannot be saved.

2. Survives without charging (\(A_i > L + Y\)): The battery after \(Y\) hours is \(A_i - Y > L\), so it survives without any charging. No need to use a mobile battery.

3. Dies without charging (\(L < A_i \leq L + Y\)): Currently alive, but after \(Y\) hours \(A_i - Y \leq L\), so it will turn off. It can be saved by connecting a mobile battery.

Greedy Strategy

Let’s consider a concrete example. For \(N=5, L=10, K=2, Y=5, A = [20, 8, 16, 12, 30]\):

• \(A_2 = 8 \leq 10 = L\): Already dead
• \(A_5 = 30 > 15 = L+Y\): Survives without charging
• \(A_1 = 20 > 15\): Survives without charging
• \(A_3 = 16 > 15\): Survives without charging
• \(A_4 = 12\): \(10 < 12 \leq 15\), so charging is needed

There is 1 smartphone in category 3, and since \(K=2\), we can save all of them. The answer is \(3 + 1 = 4\) smartphones.

The optimal strategy is to prioritize assigning mobile batteries to category 3 devices. Category 2 doesn’t need them, and category 1 cannot be saved.

Algorithm

1. Classify each smartphone into the 3 categories
2. Count the number of category 2 (survives without charging) smartphones → \(S\)
3. Count the number of category 3 (needs charging) smartphones → \(C\)
4. The number of smartphones that can be saved by mobile batteries is \(\min(K, C)\)
5. The answer is \(S + \min(K, C)\)

Complexity

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

Implementation Notes

• Be careful with the survival boundary: Since “the phone turns off at \(L\)% or below,” survival means “\(> L\)”. Be careful that it’s \(> L\), not \(\geq L\).

• Exclude already dead smartphones: Devices with \(A_i \leq L\) won’t revive even with a mobile battery, so they must be excluded first.

• When \(K\) exceeds the number of category 3 devices: Connecting extra ports to category 2 devices has no effect, so we cap it with \(\min(K, C)\).

  Source Code

N, L, K, Y = map(int, input().split())
A = list(map(int, input().split()))

# Each phone loses Y% over Y hours (1% per hour)
# Phone dies when battery <= L (exactly L means it dies)
# So phone i survives without charging if A_i - Y > L, i.e., A_i - Y >= L + 1, i.e., A_i > L + Y
# Phone connected to mobile battery never loses charge, so it survives as long as A_i > L
# Wait: "バッテリー残量がL%以下になると電源が切れて使えなくなります"
# Current battery is A_i. If A_i <= L already, phone is already dead even if connected?
# Actually, "ちょうどL%になった瞬間に電源が切れます" - so at L% it dies.
# If A_i > L, connecting to mobile battery keeps it alive (no consumption).
# If A_i <= L, the phone is already dead or dies at L%.
# Wait, A_i could be > L currently. Let me re-read.
# "バッテリー残量がL%以下になると電源が切れる" and "ちょうどL%になった瞬間に電源が切れる"
# So the phone dies when battery reaches L%. If A_i > L, it's currently alive.
# If A_i == L or A_i < L... but A_i >= 1 and L can be 0..99.
# If A_i <= L, the phone is already at or below L%, so it's already dead.

# Categories:
# 1. Already dead (A_i <= L): can't be saved, count = 0
# 2. Alive and survives without charging: A_i - Y > L, i.e., A_i > L + Y (after Y hours, battery = A_i - Y > L)
#    Wait: dies when reaching L, so survives if A_i - Y > L, i.e., A_i > L + Y
#    Actually: "L%以下になると電源が切れる" means <= L dies. So survives if battery > L after Y hours.
#    After Y hours: A_i - Y. Survives if A_i - Y > L, i.e., A_i > L + Y.
# 3. Alive but will die without charging: A_i > L but A_i <= L + Y
#    These need mobile battery to survive.

# Strategy: 
# - Phones with A_i <= L: dead, nothing to do
# - Phones with A_i > L + Y: survive without mobile battery
# - Phones with L < A_i <= L + Y: need mobile battery to survive
# We should connect mobile battery to as many of category 3 as possible (up to K).
# If K > number of category 3 phones, extra connections don't help (category 2 already survives).

alive = [a for a in A if a > L]
survive_without = sum(1 for a in alive if a > L + Y)
need_charging = sum(1 for a in alive if a <= L + Y)

charged = min(K, need_charging)
print(survive_without + charged)

---

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