概要

各中継器で信号強度が \(C \leftarrow \left\lfloor C \times A_i / 100 \right\rfloor\) と更新されるので、これを先頭から順番にシミュレーションして最終値を求める問題です。

考察

• 中継器 \(i\) を通過した後の強度は「現在の強度 \(C\) に効率 \(A_i\%\) を掛けて小数点以下切り捨て」です。
  つまり更新式はそのまま $\( C \leftarrow \left\lfloor \frac{C \times A_i}{100} \right\rfloor \)$ になります。
• \(N \le 10^5\) なので、各中継器についてこの計算を1回ずつ行う素朴なシミュレーションで十分間に合います（\(10^5\) 回の整数演算）。
• 逆に、全体をまとめて「\(M \times \prod A_i / 100^N\)」のように計算しようとすると、
  • \(\prod A_i\) が巨大になりオーバーフロー（Python以外では特に）しやすい
  • 各段階の切り捨てがあるため、最後に1回切り捨てても同じ結果にならない（WAの原因） という問題があります。
    例：\(M=1, A=[50, 50]\)
    段階的：\(\lfloor 1\cdot 50/100\rfloor=0\) → 以降ずっと0
    まとめて：\(1\cdot 2500/10000=0.25\)（最後に切り捨てても0だが、一般には一致しないケースがある）
• 一度 \(C=0\) になったらその後ずっと \(0\) のままなので、そこで打ち切ると無駄な計算を省けます。

アルゴリズム

1. 現在の信号強度 \(c\) を \(M\) で初期化する。
2. \(i=1\) から \(N\) まで順に、次を行う：
   • \(c \leftarrow (c \times A_i) // 100\)（// は整数除算で切り捨て）
   • もし \(c=0\) なら以降も変化しないのでループを終了する。
3. 最終的な \(c\) を出力する。

（具体例）
\(M=123, A=[80, 50]\) のとき
- 1個目：\(123 \to \lfloor 123\cdot 80/100\rfloor = 98\)
- 2個目：\(98 \to \lfloor 98\cdot 50/100\rfloor = 49\)
出力は \(49\)。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（入力配列を除けば定数）

実装のポイント

• 切り捨ては c = (c * a) // 100 のように整数演算で正確に行う（浮動小数点を使うと誤差の原因）。

• \(M \le 10^{18}\) で掛け算が出てきますが、Pythonの整数は多倍長なので安全です（他言語なら 128bit やオーバーフローに注意）。

• sys.stdin.buffer.read() を使って一括で読み込むと、\(N=10^5\) でも高速に処理できます。

• \(c==0\) で早期終了すると、最悪ケース以外で少し速くなります。

  ソースコード

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

この解説は gpt-5.2-high によって生成されました。