Overview

This problem involves processing each transaction’s “receive the sale amount then pay half (rounded down) as a fee,” which can be rephrased in terms of the actual net increase and summed up sequentially.

Analysis

Suppose the sale amount for one transaction is \(X\) yen. Following the problem statement:

• First, receive \(X\) yen (balance \(+X\))
• Immediately after, pay \(\lfloor X/2 \rfloor\) yen as a fee (balance \(-\lfloor X/2 \rfloor\))

Therefore, the net increase in balance from that transaction is [ X - \lfloor X/2 \rfloor ]

The key observation here is that [ X - \lfloor X/2 \rfloor = \lceil X/2 \rceil ] holds (for even numbers it’s exactly half, for odd numbers it’s “half plus one more”). Furthermore, in integer arithmetic, [ \lceil X/2 \rceil = \left\lfloor \frac{X+1}{2} \right\rfloor ] so in Python this can be computed as (X + 1) // 2.

For example, when \(X=5\): - Receive \(+5\) - Pay fee \(\lfloor 5/2 \rfloor = 2\), so \(-2\) - Net increase is \(3\)
This matches \(\lceil 5/2 \rceil = 3\).

Naively “receiving then subtracting the fee” each time still runs in \(O(M)\) which is fast enough, but knowing that the net increase is always \(\lceil X/2 \rceil\) allows us to consolidate the computation into a single integer operation, reducing implementation mistakes (such as handling floor division incorrectly).

Algorithm

1. Store the product prices \(P_i\) in an array.
2. Initialize the balance cash to the initial value \(S\).
3. For each customer \((T_j, Q_j)\):
   • Compute the sale amount \(X = P_{T_j} \times Q_j\)
   • Add the net increase \(\lceil X/2 \rceil = (X+1)//2\) to cash
4. Output the final cash.

Complexity

• Time complexity: \(O(N + M)\) (reading prices \(N\) times, processing transactions \(M\) times)
• Space complexity: \(O(N)\) (price array)

Implementation Notes

• Since the increase after subtracting the fee is \(\lceil X/2 \rceil\), writing cash += (x + 1) // 2 is both safe and concise.

• Since the input size can be large (up to around \(2\times 10^5\) lines), reading all input at once with sys.stdin.buffer.read() is faster.

• Making P 1-indexed (so that P[1] corresponds to product 1) allows using \(T_j\) directly as an index, reducing mistakes.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    S = next(it)

    P = [0] * (N + 1)
    for i in range(1, N + 1):
        P[i] = next(it)

    cash = S
    for _ in range(M):
        t = next(it)
        q = next(it)
        x = P[t] * q
        cash += (x + 1) // 2  # ceil(x/2)

    print(cash)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.