Overview

This is a problem of simulating the strength of a signal as it passes through \(N\) repeaters in order. At each step, you 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 an extremely large value. However, in languages that support arbitrary-precision integers, such as Python, you can compute without worrying about overflow. Additionally, since \(A_i \leq 100\) at each step, the signal strength will never exceed \(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, consider the case where the signal strength \(C\) becomes \(0\) during the process. When \(C = 0\), even after passing through the next repeater, \(\lfloor 0 \times A_i / 100 \rfloor = 0\), so the strength remains \(0\) without change. Therefore, you can terminate the computation early (break) as soon as the strength reaches \(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 for \(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 completes with a single pass through 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\), unnecessary computations can be avoided, 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.