Overview

At each repeater, the signal strength is updated as \(C \leftarrow \left\lfloor C \times A_i / 100 \right\rfloor\), so this is a problem where you simulate this from the beginning in order to find the final value.

Analysis

• The strength after passing through repeater \(i\) is “the current strength \(C\) multiplied by efficiency \(A_i\%\), rounded down (floor).”
  In other words, the update formula is simply $\( C \leftarrow \left\lfloor \frac{C \times A_i}{100} \right\rfloor \)$
• Since \(N \le 10^5\), a straightforward simulation performing this calculation once for each repeater is more than sufficient (\(10^5\) integer operations).
• Conversely, if you try to compute everything at once like “\(M \times \prod A_i / 100^N\)”:
  • \(\prod A_i\) becomes enormous and is prone to overflow (especially in languages other than Python)
  • Because there is a floor operation at each stage, taking the floor only once at the end does not yield the same result (a cause of WA)

Example: \(M=1, A=[50, 50]\)
Step-by-step: \(\lfloor 1\cdot 50/100\rfloor=0\) → stays 0 from then on
All at once: \(1\cdot 2500/10000=0.25\) (taking the floor at the end also gives 0, but in general there are cases where the results differ) - Once \(C=0\), it remains \(0\) forever, so you can break early to avoid unnecessary computation.

Algorithm

1. Initialize the current signal strength \(c\) to \(M\).
2. For \(i=1\) to \(N\) in order, do the following:
   • \(c \leftarrow (c \times A_i) // 100\) (// denotes integer division with floor)
   • If \(c=0\), since nothing will change from this point on, exit the loop.
3. Output the final value of \(c\).

(Concrete example)
When \(M=123, A=[80, 50]\):
- 1st repeater: \(123 \to \lfloor 123\cdot 80/100\rfloor = 98\)
- 2nd repeater: \(98 \to \lfloor 98\cdot 50/100\rfloor = 49\)
Output is \(49\).

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\) (constant aside from the input array)

Implementation Notes

• Perform the floor operation accurately using integer arithmetic like c = (c * a) // 100 (using floating-point numbers can cause precision errors).

• Since \(M \le 10^{18}\) and multiplications are involved, Python’s arbitrary-precision integers handle this safely (in other languages, be careful about 128-bit types or overflow).

• Using sys.stdin.buffer.read() to read all input at once allows fast processing even for \(N=10^5\).

• Early termination when \(c==0\) provides a slight speedup for cases other than the worst case.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M = data[0], data[1]
    A = data[2:2+N]
    c = M
    for a in A:
        c = (c * a) // 100
        if c == 0:
            break
    print(c)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.