Overview

Given income \(S_i\) with a progressive tax system where the tax rate changes at a boundary \(L\), calculate the tax according to its definition and output each person’s tax amount \(T_i\).

Analysis

The key point of this problem is to split the income into “the first \(L\) yen” and “the portion exceeding \(L\) yen,” apply the respective tax rates, sum them up, and then perform the floor operation only once at the end.

• When \(S \le L\), it is simply \(T=\left\lfloor \dfrac{S\cdot P}{100}\right\rfloor\).
• When \(S > L\),
  \(T=\left\lfloor \dfrac{L\cdot P+(S-L)\cdot Q}{100}\right\rfloor\).

An important thing to note is that you must NOT “divide \(L\cdot P\) and \((S-L)\cdot Q\) each by \(100\), floor them separately, and then add them together.”
For example (an extreme case), if \(L=1, P=50, Q=50, S=2\): - Correct calculation: \(\left\lfloor \dfrac{1\cdot 50 + 1\cdot 50}{100}\right\rfloor=\lfloor 1 \rfloor = 1\) - Incorrect separate flooring: \(\left\lfloor \dfrac{50}{100}\right\rfloor+\left\lfloor \dfrac{50}{100}\right\rfloor = 0+0=0\)
The results differ. Therefore, “sum first, then // 100” is essential.

Also, since \(N\le 10^5\), computing each person’s tax in \(O(1)\) is more than sufficient. In fact, in Python, I/O tends to be the bottleneck, so it is safer to use fast input (bulk reading).

Algorithm

For each income \(S\), do the following:

1. The low tax rate portion (up to \(L\)):
   \(low = \min(S, L)\)
2. The high tax rate portion (the amount exceeding \(L\)):
   \(high = \max(0, S-L)\)
3. Compute the tax by flooring the total at once according to the definition:
   \(tax = \dfrac{low\cdot P + high\cdot Q}{100}\) floored, i.e.,
   tax = (low * P + high * Q) // 100
4. Output this for all people.

Complexity

• Time complexity: \(O(N)\) (\(O(1)\) computation per person)
• Space complexity: \(O(N)\) (to store results in an array for output)

Implementation Notes

• The floor operation must be performed “only once after summing,” as in (low * P + high * Q) // 100.

• The value range is \(S,L\le 10^9\) and the tax rate \(\le 100\), so the product is at most around \(10^{11}\). Python’s integers handle this safely, but in other languages, it is advisable to use 64-bit integers (long long).

• For \(N=10^5\), rather than calling input() repeatedly, it is faster to read all input at once with sys.stdin.buffer.read() and output everything at once with "\n".join(...).

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, L, P, Q = data[0], data[1], data[2], data[3]
    res = []
    idx = 4
    for _ in range(N):
        s = data[idx]
        idx += 1
        low = s if s <= L else L
        high = 0 if s <= L else s - L
        tax = (low * P + high * Q) // 100
        res.append(str(tax))
    sys.stdout.write("\n".join(res))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.