Overview

On a one-dimensional billiard table \([0, M]\), we need to find the ball’s position after each shot and the total number of reflections.

Simulating reflections one by one is too slow when the distance \(A_i\) is large, so we process each shot in \(O(1)\) by “unfolding the table into a straight line instead of reflecting.”

Approach

Unfolding the table into a straight line

Billiard reflections become easier to handle with the following idea.

If we repeatedly mirror-flip the interval \([0, M]\) and lay the copies side by side, then a ball bouncing back and forth can be viewed as simply traveling in a straight line on this extended line.

For example, when moving to the right by distance \(A\), if the current position is \(pos\), then the destination on the extended line is

\(pos + A\)

If moving to the left, it is

\(pos - A\)

Then, by folding that coordinate back into the original interval \([0, M]\), we can determine the actual position.

Since the period is \(2M\), for a coordinate \(x\):

• \(r = x \bmod 2M\)
• If \(r \leq M\), the position is \(r\)
• If \(r > M\), the position is \(2M - r\)

For example, when \(M = 10\), the correspondence between extended coordinates and actual positions is as follows:

Extended coordinate	Actual position
\(0\)	\(0\)
\(5\)	\(5\)
\(10\)	\(10\)
\(12\)	\(8\)
\(17\)	\(3\)
\(20\)	\(0\)

Counting reflections

A reflection occurs when the ball reaches an endpoint \(0\) or \(M\) and still has remaining travel distance.

On the extended line, the locations corresponding to endpoints are all

multiples of \(M\).

In other words, by counting the number of multiples of \(M\) passed through during movement, we can determine the number of reflections.

However, there are some caveats:

• If the ball lands exactly on an endpoint at the end of a shot, the movement ends there, so no reflection occurs
• If the ball is shot outward from an endpoint, it immediately reflects without consuming travel distance, and this counts as a reflection
• If \(A_i = 0\), no reflection or movement occurs

Therefore, we need to slightly adjust the boundaries of the counting interval.

Why the naive method is slow

With a method that updates position and direction at each reflection, a single shot can cause up to approximately \(A_i / M\) reflections.

Given the constraints

\(A_i \leq 10^9\), \(N \leq 2 \times 10^5\)

processing reflections one by one can result in an extremely large number of operations in the worst case, leading to TLE.

Instead, for each shot, we compute “how many multiples of \(M\) are passed through” all at once using a formula.

Algorithm

Let the current position be \(pos\) and the total number of reflections be \(reflections\).

Also, let the period be

\(period = 2M\)

Counting multiples of \(M\)

Consider a function that computes the number of multiples of \(M\) contained in the integer interval \([lo, hi]\).

This can be calculated as

\(\left\lfloor \frac{hi}{M} \right\rfloor - \left\lceil \frac{lo}{M} \right\rceil + 1\)

In code, this is the following function:

def count_multiples(lo, hi):
    if lo > hi:
        return 0
    return hi // M - ((lo + M - 1) // M) + 1

If \(lo > hi\), the interval is empty, so the count is \(0\).

Right-directed shot

For a right-directed shot with distance \(A\), the endpoint on the extended line is

\(end = pos + A\)

Reflections occur when multiples of \(M\) are crossed.

However, even if the final point \(end\) is exactly a multiple of \(M\), the movement ends there, so no reflection occurs.

Therefore, we basically count the multiples of \(M\) in \([pos+1, end-1]\).

However, if the starting position is \(M\) and the direction is right, it is outward-facing, so an immediate reflection occurs.

In that case, we include the starting point \(pos\) in the count.

if c == b'R':
    end = pos + A

    if pos == M:
        reflections += count_multiples(pos, end - 1)
    else:
        reflections += count_multiples(pos + 1, end - 1)

Left-directed shot

For a left-directed shot with distance \(A\), the endpoint on the extended line is

\(end = pos - A\)

Since coordinates decrease when moving left, the range passed through is \([end, pos]\).

However, the final point \(end\) does not cause a reflection, so it is excluded.

We basically count the multiples of \(M\) in \([end+1, pos-1]\).

However, if the starting position is \(0\) and the direction is left, it is outward-facing, so an immediate reflection occurs.

In that case, we include the starting point \(pos\) in the count.

else:
    end = pos - A

    if pos == 0:
        reflections += count_multiples(end + 1, pos)
    else:
        reflections += count_multiples(end + 1, pos - 1)

Updating the final position

Once the endpoint \(end\) on the extended line is known, we fold it back with period \(2M\).

r = end % period

if r <= M:
    pos = r
else:
    pos = period - r

Python’s % operator returns a non-negative remainder even for negative numbers, so it works directly even when \(end\) becomes negative from moving left.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\)

Since each shot is processed in constant time, the overall complexity is \(O(N)\).

Implementation Notes

• For shots with \(A_i = 0\), neither the position nor the reflection count changes, so we continue at the beginning.

• Even if the ball reaches an endpoint at the end of a shot, no reflection is counted, so the endpoint is excluded from the reflection counting range.

• When shooting outward from an endpoint, the reflection at the starting point must be counted.

• The reflection count can become large, so in other languages, 64-bit integers such as long long must be used.

  Source Code

import sys

input = sys.stdin.buffer.readline

N, M, pos = map(int, input().split())
period = 2 * M
reflections = 0

def count_multiples(lo, hi):
    if lo > hi:
        return 0
    return hi // M - ((lo + M - 1) // M) + 1

for _ in range(N):
    c, a = input().split()
    A = int(a)
    if A == 0:
        continue

    if c == b'R':
        end = pos + A
        if pos == M:
            reflections += count_multiples(pos, end - 1)
        else:
            reflections += count_multiples(pos + 1, end - 1)

        r = end % period
    else:
        end = pos - A
        if pos == 0:
            reflections += count_multiples(end + 1, pos)
        else:
            reflections += count_multiples(end + 1, pos - 1)

        r = end % period

    if r <= M:
        pos = r
    else:
        pos = period - r

print(pos, reflections)

---

This editorial was generated by gpt-5.5-medium.