Overview

This problem asks us to simulate the process where a signal passes through \(N\) repeaters in order, with the signal strength attenuating by a fixed ratio at each repeater, and find the final signal strength.

Analysis

Understanding the Problem

When a signal with strength \(C\) passes through repeater \(i\), the new strength becomes \(\lfloor C \times A_i / 100 \rfloor\). This means “the signal is transmitted with \(A_i\) percent efficiency.”

Verification with a Concrete Example

For example, with \(M = 1000\), \(N = 3\), \(A = [50, 80, 90]\): 1. Initial strength: \(C = 1000\) 2. After repeater 1: \(C = \lfloor 1000 \times 50 / 100 \rfloor = 500\) 3. After repeater 2: \(C = \lfloor 500 \times 80 / 100 \rfloor = 400\) 4. After repeater 3: \(C = \lfloor 400 \times 90 / 100 \rfloor = 360\)

Why Simple Simulation Works

In this problem, we need to process each repeater one by one in order.

• There are at most \(10^5\) repeaters
• The computation at each repeater is \(O(1)\) (only multiplication and division)

Therefore, the total time complexity is \(O(N)\), which is sufficiently fast.

Important Note: Handling the Floor Function

The expression \(\lfloor C \times A_i / 100 \rfloor\) in the problem means “floor division.” Python’s // operator performs floor division for integer operands, so writing C * a // 100 will compute the correct result.

Algorithm

1. Initialize the signal strength \(C\) with the initial value \(M\)
2. For each repeater \(i = 1, 2, \ldots, N\) in order, do the following:
   • \(C \leftarrow \lfloor C \times A_i / 100 \rfloor\)
3. Output the final value of \(C\)

C = M
for each a in A:
    C = floor(C * a / 100)
output C

Complexity

• Time complexity: \(O(N)\)
  • We perform \(O(1)\) computation for each of the \(N\) repeaters
• Space complexity: \(O(N)\)
  • \(O(N)\) space is needed to store the array \(A\)
  • (This can be reduced to \(O(1)\) with stream processing)

Implementation Tips

• Use integer arithmetic: In Python, using // performs integer floor division. Avoid using / as it produces floating-point numbers, which may cause precision issues.

• Handling large numbers: \(M\) can be as large as \(10^{18}\), but Python supports arbitrary-precision integers, so there’s no need to worry about overflow. Be careful when using languages like C++.

• Multiply first: By computing in the order C * a // 100, we maintain precision and get the correct result. If we computed a // 100 first, it would become 0 when \(a < 100\).

  Source Code

N, M = map(int, input().split())
A = list(map(int, input().split()))

C = M
for a in A:
    C = C * a // 100

print(C)

---

This editorial was generated by claude4.5opus.