Overview

This problem requires calculating the tax amount for each taxpayer’s income according to a progressive taxation formula. We determine the tax by branching on whether the income is at most the threshold \(L\) or exceeds it, then applying the floor function (truncation) to compute the tax amount.

Analysis

Problem Breakdown

This problem is a simulation of progressive taxation with two tax brackets. The key points are as follows:

• If income \(S\) is at most \(L\), apply tax rate \(P\) % to the entire amount
• If income \(S\) exceeds \(L\), apply tax rate \(P\) % to the first \(L\) yen, and tax rate \(Q\) % to the excess \((S - L)\) yen
• Truncation (floor) is applied only once at the end (not individually to each part)

Verification with a Concrete Example

When \(L = 100\), \(P = 10\), \(Q = 23\), \(S = 150\):

\[T = \left\lfloor \frac{100 \times 10 + 50 \times 23}{100} \right\rfloor = \left\lfloor \frac{1000 + 1150}{100} \right\rfloor = \left\lfloor 21.5 \right\rfloor = 21\]

Is a Naive Approach Sufficient?

Since we can compute the tax for each taxpayer in constant time, processing \(N\) people in a loop takes \(O(N)\). With \(N \leq 10^5\), this is fast enough.

Watch Out for Overflow

\(S\) and \(L\) can be up to \(10^9\), and \(P, Q\) can be up to \(100\), so \(L \times P\) or \((S - L) \times Q\) can reach approximately \(10^{11}\). In Python, integers have no upper limit, so this is not an issue, but in C++ and similar languages, 64-bit integers must be used.

Algorithm

1. Read \(N, L, P, Q\)
2. For each taxpayer \(i\), read income \(S_i\) and compute the tax based on the following cases:
   • If \(S_i \leq L\): \(T_i = \lfloor S_i \times P \div 100 \rfloor\)
   • If \(S_i > L\): \(T_i = \lfloor (L \times P + (S_i - L) \times Q) \div 100 \rfloor\)
3. Python’s integer division // coincides with the floor function for non-negative integers, so it can be used directly
4. Output each tax amount

Complexity

• Time complexity: \(O(N)\) — constant-time computation for each taxpayer
• Space complexity: \(O(N)\) — storing results in a list for output (can be \(O(1)\) if outputting sequentially)

Implementation Notes

• Fast input: By reading all input at once with sys.stdin.read() and splitting with split(), large amounts of input are processed efficiently. This is faster than calling input() \(N\) times.

• Fast output: Results are accumulated in a list and output all at once at the end with '\n'.join(out). This avoids the overhead of calling print() \(N\) times.

• Behavior of integer division //: Python’s // operator truncates toward negative infinity, but since \(S \times P\) and \(L \times P + (S-L) \times Q\) are all non-negative, this coincides with standard truncation (floor function) and causes no issues.

• Timing of truncation: As noted in the problem statement, \(L \times P\) and \((S-L) \times Q\) must be added together first before dividing by \(100\). Dividing each part individually and then adding can produce different results, so caution is needed.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    L = int(input_data[idx]); idx += 1
    P = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    out = []
    for i in range(N):
        S = int(input_data[idx]); idx += 1
        if S <= L:
            tax = S * P // 100
        else:
            tax = (L * P + (S - L) * Q) // 100
        out.append(str(tax))
    
    print('\n'.join(out))

main()

---

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