Overview

This is a problem where you need to find the minimum total number of cooling packs required to bring the temperatures of \(N\) rooms all to \(M\) degrees or below, using cooling packs (each one lowers the temperature by \(D\) degrees).

Analysis

The key insight for solving this problem is that “each room can be considered independently.” Since using a cooling pack on one room does not affect the temperature of other rooms, we can calculate “the minimum number of packs needed to bring temperature \(T_i\) to \(M\) degrees or below” for each room \(i\), and sum them up to get the answer.

Calculating the Required Number of Packs

If room \(i\)’s temperature \(T_i\) is already \(M\) degrees or below, the required number of packs is \(0\). If \(T_i\) is higher than \(M\) degrees, the temperature needs to be lowered by at least \(T_i - M\) degrees. Since each cooling pack lowers the temperature by \(D\) degrees, the required number is as follows:

\[(\text{required packs}) = \lceil (T_i - M) / D \rceil\]

Here, \(\lceil \cdot \rceil\) denotes the “ceiling” (rounding up). For example, if you need to lower the temperature by 5 degrees and each pack lowers it by 2 degrees, you need \(\lceil 5 / 2 \rceil = 3\) packs (because 2 packs would only lower it by 4 degrees, which is not enough to reach the target).

Efficient Computation

Since \(N\) can be as large as \(10^5\), we need an \(O(N)\) algorithm that processes each room one at a time. Also, since temperatures and the pack performance \(D\) can be as large as \(10^9\), we must use division to compute the result directly, rather than simulating by subtracting one degree at a time.

Algorithm

1. Initialize the total pack count total_packs to \(0\).
2. For each room’s temperature \(T_i\), repeat the following:
   • If \(T_i > M\):
     • Compute the temperature difference to reduce: \(diff = T_i - M\).
     • Compute the required number of packs: \(packs\_needed = \lceil diff / D \rceil\).
     • Add \(packs\_needed\) to total_packs.
3. Output the final total_packs.

Complexity

• Time complexity: \(O(N)\)
  • Since each room’s calculation takes constant time, the total time is proportional to the number of rooms \(N\).
• Space complexity: \(O(N)\)
  • If the \(N\) input temperatures are stored in a list, the memory required is proportional to \(N\).

Implementation Notes

Integer Ceiling Division

When computing “the ceiling of \(A / B\)” using integer types in a programming language, using floating-point numbers may introduce errors, so the following integer arithmetic technique is commonly used:

packs_needed = (diff + D - 1) // D

By using this formula, when diff is divisible by D, the result is diff // D, and when it is not divisible, the result is (diff // D) + 1, thus correctly obtaining the ceiling.

Fast Input/Output

When handling input of around \(N=10^5\) in Python, reading all input at once using sys.stdin.read().split() is faster than repeatedly calling input(), which can reduce execution time.

Source Code

import sys

def solve():
    # 標準入力からすべてのデータを取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N, M, D を取得
    N = int(input_data[0])
    M = int(input_data[1])
    D = int(input_data[2])
    
    # 各部屋の温度 T_i を取得
    T = input_data[3:]
    
    total_packs = 0
    for i in range(N):
        temp = int(T[i])
        # 現在の温度が目標温度 M より高い場合のみ冷却パックが必要
        if temp > M:
            diff = temp - M
            # 必要な冷却パックの数は ceil(diff / D)
            # 整数切り上げの計算: (A + B - 1) // B
            packs_needed = (diff + D - 1) // D
            total_packs += packs_needed
            
    # 結果を出力
    print(total_packs)

if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3-flash-preview.