Overview

Given \(N\) taxpayers, different tax rates are applied to the portion of income at or below the threshold \(L\) and the portion exceeding \(L\). The task is to compute each taxpayer’s total tax amount (rounded down to the nearest integer).

Analysis

The key point of this problem is to accurately translate the given formula into code.

1. Verifying the Formula

The tax \(T\) for an income \(S\) is calculated using the following conditional:

• When income is \(L\) yen or less (\(S \leq L\)): $\(T = \lfloor (S \times P) / 100 \rfloor\)$
• When income exceeds \(L\) yen (\(S > L\)): $\(T = \lfloor (L \times P + (S - L) \times Q) / 100 \rfloor\)$

The important point here is that when income exceeds \(L\) yen, the “tax on the first \(L\) yen” and the “tax on the amount exceeding \(L\) yen” are summed together, and the floor operation is applied only at the end. If you apply floor operations individually at intermediate steps, rounding errors may occur, so you need to compute the entire numerator first before dividing by 100.

2. Constraints and Data Types

• The number of taxpayers \(N\) is at most \(10^5\), so each taxpayer must be processed in \(O(1)\) (constant time), solving the entire problem in \(O(N)\).
• Income \(S\) and threshold \(L\) can be up to \(10^9\), and intermediate calculations (such as \(S \times P\)) can grow to around \(10^{11}\). Python’s integer type (int) is automatically handled as arbitrary-precision integers, so there is no concern about overflow. However, in other languages (such as C++), you need to use a 64-bit integer type (long long).

Algorithm

1. Read \(N, L, P, Q\) from input.
2. For each of the \(N\) incomes \(S_i\), repeat the following:
   • If \(S_i \leq L\), compute tax = (S_i * P) // 100.
   • Otherwise (if \(S_i > L\)), compute tax = (L * P + (S_i - L) * Q) // 100.
   • Record the computed tax.
3. After processing all taxpayers, output the results in order.

※ Python’s // operator behaves the same as the floor function (rounding down) for positive numbers.

Complexity

• Time complexity: \(O(N)\) Since we perform one calculation for each of the \(N\) incomes, the processing completes in time proportional to the number of taxpayers.
• Space complexity: \(O(N)\) When reading all input at once and storing the results in a list for output, memory proportional to the number of taxpayers is used.

Implementation Tips

• Fast I/O: Since \(N\) can be as large as \(10^5\), in Python, instead of calling input() repeatedly, reading all input at once with sys.stdin.read().split() and outputting all at once with sys.stdout.write() can significantly reduce execution time.

• Precomputing common values: The value \(L \times P\) appearing in the formula for \(S > L\) is the same for all taxpayers. By precomputing it outside the loop, you can achieve a slight efficiency improvement.

• Avoiding floating-point numbers: Instead of using / 100 followed by math.floor(), using integer division // 100 completely avoids precision issues caused by floating-point arithmetic.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白文字で分割します。
    # Nが10^5程度であれば、一括で読み込むのが効率的です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 1行目のパラメータ（N, L, P, Q）を取得します。
    # N: 納税者の人数
    # L: 税率が変わる境界の所得額
    # P: L円以下の部分に適用される税率 (%)
    # Q: L円を超える部分に適用される税率 (%)
    n = int(input_data[0])
    l = int(input_data[1])
    p = int(input_data[2])
    q = int(input_data[3])
    
    # 所得がLを超える場合の計算で繰り返し使われる L * P をあらかじめ計算しておきます。
    lp = l * p
    
    # 各納税者の税額を計算し、結果を格納するリストです。
    results = []
    
    # 各納税者の所得額 S_i は input_data の 5番目（インデックス4）から順に格納されています。
    for i in range(n):
        s = int(input_data[4 + i])
        
        if s <= l:
            # 所得が L 円以下の場合：
            # 税額 = floor(所得 * P / 100)
            tax = (s * p) // 100
        else:
            # 所得が L 円を超える場合：
            # L円以下の部分に P%、それを超える部分 (s - L) に Q% を適用します。
            # 税額 = floor((L * P + (s - L) * Q) / 100)
            tax = (lp + (s - l) * q) // 100
        
        # 数値を文字列に変換してリストに追加します（最後の一括出力のため）。
        results.append(str(tax))
    
    # すべての計算結果を改行で連結し、一括で標準出力に書き出します。
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

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