Overview

This problem asks you to simulate a signal passing through \(N\) repeaters in order, where the strength is attenuated by a fixed ratio at each repeater, and to 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.”

Verifying with a Concrete Example

For example, if \(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 a Simple Simulation Is Sufficient

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 fast enough.

Note: Handling the Floor Function

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

Algorithm

1. Initialize the signal strength \(C\) to the initial value \(M\)
2. For each repeater \(i = 1, 2, \ldots, N\), do the following in order:
   • \(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 an \(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)\) by using stream processing)

Implementation Notes

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

• Handling large numbers: \(M\) can be up to \(10^{18}\), but Python supports arbitrary-precision integers, so there is no concern about overflow. Be careful if using languages like C++.

• Multiply first: By computing in the order C * a // 100, we maintain precision and obtain the correct result. If you compute 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.