Overview

At each relay, the signal strength is updated as \(C \leftarrow \left\lfloor C \times A_i / 100 \right\rfloor\). This problem asks you to simulate this process sequentially from the first relay to find the final value.

Analysis

• The strength after passing through relay \(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 relay is fast enough (\(10^5\) integer operations).
• Conversely, if you try to compute everything at once as “\(M \times \prod A_i / 100^N\)”, the following problems arise:
  • \(\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, applying 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\) → remains 0 from that point on
All at once: \(1\cdot 2500/10000=0.25\) (flooring at the end also gives 0 here, but in general there are cases where the results differ) - Once \(C=0\), it stays \(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\), do the following:
   • \(c \leftarrow (c \times A_i) // 100\) (// denotes integer division with floor)
   • If \(c=0\), further iterations won’t change the value, so break out of the loop.
3. Output the final value of \(c\).

(Concrete example)
When \(M=123, A=[80, 50]\):
- 1st relay: \(123 \to \lfloor 123\cdot 80/100\rfloor = 98\)
- 2nd relay: \(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 precisely using integer arithmetic like c = (c * a) // 100 (using floating-point arithmetic can cause precision errors).

• Although \(M \le 10^{18}\) and multiplications occur, Python’s integers have arbitrary precision so this is safe (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 in non-worst-case scenarios.

  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.