概要

\(N\) 個の中継器を順番に通過する信号の強度をシミュレーションする問題です。各ステップで与えられた伝送効率 \(A_i\) を掛け、100で割ったあとの整数部分（床関数）を取る操作を繰り返します。

考察

この問題のポイントは、「現在の信号強度に対して、各中継器の操作を順番に適用していく」という素直なシミュレーションで解ける点にあります。

1. 数値の大きさ

最初の信号強度 \(M\) は最大で \(10^{18}\) と非常に大きな値ですが、Pythonなどの多倍長整数をサポートしている言語であれば、オーバーフローを気にせずに計算できます。また、各ステップで \(A_i \leq 100\) であるため、信号強度が \(M\) を超えることはありません。

2. 計算の効率化

中継器の数 \(N\) は最大 \(10^5\) です。各中継器での計算は定数時間で行えるため、全体で \(O(N)\) の計算量となり、制限時間内に十分間に合います。

さらに効率化を考えるなら、途中で信号の強度 \(C\) が \(0\) になった場合に注目します。 \(C = 0\) のとき、次の中継器を通過しても \(\lfloor 0 \times A_i / 100 \rfloor = 0\) となり、強度は \(0\) のまま変化しません。そのため、強度が \(0\) になった時点で計算を打ち切る（breakする）ことができます。

アルゴリズム

1. 現在の信号強度 current_strength を \(M\) で初期化します。
2. 各中継器の伝送効率 \(A_i\) について、以下の処理を \(i = 1\) から \(N\) まで繰り返します：
   • もし current_strength が \(0\) ならば、繰り返しを終了します。
   • current_strength を (current_strength * A_i) // 100 に更新します。
3. 最終的な current_strength を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 中継器の数 \(N\) に対して、1回ずつのループで計算が完了します。
• 空間計算量: \(O(N)\)
  • 入力された \(A_i\) をすべてリストに保持する場合、\(O(N)\) のメモリを使用します。

実装のポイント

• 床関数の処理: 問題文にある \(\lfloor C \times A_i / 100 \rfloor\) は、Pythonでは整数除算演算子 // を使うことで簡潔に表現できます。

• 高速な入力: \(N\) が \(10^5\) 程度と大きいため、大量の数値を読み込む際は sys.stdin.read().split() を使用して一括で取得すると実行時間を短縮できます。

• 早期終了: 強度が \(0\) になった瞬間にループを抜ける処理を入れることで、特に \(A_i\) が小さい値で続く場合に無駄な計算を省くことができます。

  ソースコード

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()

---

この解説は gemini-3-flash-preview によって生成されました。