Overview

This is a problem about simulating the strength of a signal that passes through \(N\) repeaters in sequence. At each step, we multiply by the given transmission efficiency \(A_i\), divide by 100, and take the integer part (floor function), repeating this operation.

Analysis

The key point of this problem is that it can be solved with a straightforward simulation of “applying each repeater’s operation in order to the current signal strength.”

1. Magnitude of Values

The initial signal strength \(M\) can be as large as \(10^{18}\), which is a very large value, but in languages that support arbitrary-precision integers such as Python, we can compute without worrying about overflow. Also, since \(A_i \leq 100\) at each step, the signal strength never exceeds \(M\).

2. Computational Efficiency

The number of repeaters \(N\) is at most \(10^5\). Since the computation at each repeater takes constant time, the overall time complexity is \(O(N)\), which is well within the time limit.

For further optimization, we can focus on the case where the signal strength \(C\) becomes \(0\) during the process. When \(C = 0\), passing through the next repeater gives \(\lfloor 0 \times A_i / 100 \rfloor = 0\), so the strength remains \(0\) unchanged. Therefore, we can terminate the computation early (break) as soon as the strength becomes \(0\).

Algorithm

1. Initialize the current signal strength current_strength to \(M\).
2. For each repeater’s transmission efficiency \(A_i\), repeat the following process from \(i = 1\) to \(N\):
   • If current_strength is \(0\), terminate the loop.
   • Update current_strength to (current_strength * A_i) // 100.
3. Output the final current_strength.

Complexity

• Time complexity: \(O(N)\)
  • The computation is completed with a single loop over the \(N\) repeaters.
• Space complexity: \(O(N)\)
  • If all input values \(A_i\) are stored in a list, \(O(N)\) memory is used.

Implementation Notes

• Floor function handling: The expression \(\lfloor C \times A_i / 100 \rfloor\) from the problem statement can be concisely expressed in Python using the integer division operator //.

• Fast input: Since \(N\) can be as large as \(10^5\), when reading a large number of values, using sys.stdin.read().split() to read them all at once can reduce execution time.

• Early termination: By adding a check to break out of the loop the moment the strength becomes \(0\), we can avoid unnecessary computation, especially when consecutive \(A_i\) values are small.

  Source Code

import sys

def main():
    # 標準入力からすべてのデータを読み込み、空白文字で分割してリスト化します
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は終了します
    if not input_data:
        return
    
    # N: 中継器の個数
    # M: 最初の信号の強度
    n = int(input_data[0])
    m = int(input_data[1])
    
    # 各中継器の伝送効率 A_i をイテレータとして取得します
    # これにより、大量のデータを効率的に処理できます
    a_iterator = iter(input_data[2:])
    
    current_strength = m
    
    # 各中継器を順番に通過させます
    for _ in range(n):
        # 信号強度が 0 になった場合、それ以降の中継器を通過しても 0 のままなので
        # 計算を打ち切ることができます
        if current_strength == 0:
            break
        
        # 伝送効率 A_i を取得
        try:
            a = int(next(a_iterator))
        except StopIteration:
            break
            
        # 信号の強度を更新: floor(C * Ai / 100)
        # Pythonの // 演算子は正の数に対して床関数（floor）として動作します
        current_strength = (current_strength * a) // 100
        
    # 最終的な信号の強度を出力します
    print(current_strength)

if __name__ == "__main__":
    main()

---

This editorial was generated by gemini-3-flash-preview.