Overview

This is a problem where you need to find the minimum number of cooling packs (each one lowers the temperature by \(D\) degrees) to bring all rooms to \(M\) degrees or below, given that each room has temperature \(T_i\).

Analysis

The key observation is that “rooms are independent of each other.” A cooling pack only lowers the temperature of “one chosen room,” so the number of packs used on one room does not affect other rooms. Therefore, minimizing the number needed for each room individually and summing them up gives the overall minimum.

A naive approach of “repeatedly using one pack at a time to lower by \(D\) while the temperature exceeds \(M\)” for each room would require up to \(10^9\) operations in cases like \(T_i = 10^9\) and \(D = 1\), which would certainly result in a time limit exceeded (TLE).

Instead of repeated operations, we compute “how many are needed” directly with a formula. When room \(i\) has temperature \(T_i > M\), the excess is \(x = T_i - M\). Since each pack reduces the temperature by \(D\), the required number is: - The smallest integer \(k\) satisfying \(kD \ge x\)

That is, \(k = \left\lceil \dfrac{x}{D} \right\rceil\).

The ceiling division can be computed using integer arithmetic as: [ \left\lceil \frac{x}{D} \right\rceil = \frac{x + D - 1}{D} \text{ (integer division)} ]

Also, the condition “temperature cannot go below 0 degrees” is not an issue here, since our goal is simply to reach “\(M\) or below.” Even if we overcool, it doesn’t matter, and the ceiling calculation above directly gives the minimum number of packs.

(Example) When \(M=20, D=6, T_i=35\): Excess \(x=15\), required number \(=\lceil 15/6\rceil=3\). Using 3 packs: \(35 \to 29 \to 23 \to 17\), which is \(20\) or below.

Algorithm

1. Initialize the answer \(ans=0\).
2. For each room, check the temperature \(T_i\).
   • If \(T_i \le M\), do nothing (0 packs needed).
   • If \(T_i > M\), compute the excess \(x=T_i-M\) and add the required number \(\left\lceil \dfrac{x}{D}\right\rceil = \dfrac{x + D - 1}{D}\) (integer division) to \(ans\).
3. Output \(ans\).

Complexity

• Time complexity: \(O(N)\) (each room is processed once)
• Space complexity: \(O(N)\) (to store the input array; can be reduced to \(O(1)\) if processed while reading)

Implementation Notes

• For ceiling division, use (x + D - 1) // D instead of computing ceil(x/D) with floating point (to avoid precision errors and for speed).

• Since \(N\) can be up to \(10^5\), using fast input such as sys.stdin.buffer.read() in Python is recommended.

• The total number of packs can be as large as \(N \times 10^9\), but Python’s integers have arbitrary precision, so there is no risk of overflow.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M, D = data[0], data[1], data[2]
    T = data[3:3+N]
    ans = 0
    for ti in T:
        if ti > M:
            x = ti - M
            ans += (x + D - 1) // D
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.