Overview

Given a corridor of length \(L\), each robot moves with a given initial position and velocity, bouncing off both ends. The problem asks to find each robot’s position at time \(T\).

Key Observations

In this problem, robots bounce off both ends of the corridor, so naive simulation would be extremely time-consuming. In particular, since \(T\) can be up to \(10^9\), an approach that advances time one second at a time and updates positions would never finish in time (TLE).

The crucial observation is that “a robot’s back-and-forth movement in the corridor follows a periodic pattern.” If the corridor has length \(L\), the distance required for one complete round trip is \(2L\). In other words, the robot’s movement repeats with period \(2L\).

Therefore, an effective approach is to assume the robot travels in a straight line in one direction, compute its coordinate, and then fold it back periodically to determine the actual position. This significantly reduces the time complexity.

Additionally, note that if a robot starts at an endpoint (coordinate \(0\) or \(L\)) and is facing toward the wall, a reflection occurs at time \(0\). Forgetting to handle this will result in WA.

Algorithm

For each robot, compute the position at time \(T\) using the following steps:

1. If the velocity is \(0\), the robot stays at its initial position, so output it directly.
2. If the initial position is at an endpoint:
   • If at coordinate \(0\) and \(V_i < 0\), reverse the velocity.
   • If at coordinate \(L\) and \(V_i > 0\), reverse the velocity.
3. Compute the travel distance as dist = |V_i| * T.
4. Compute a tentative final coordinate pos based on the robot’s direction:
   • If moving in the positive direction: x + dist
   • If moving in the negative direction: x - dist
5. Fold pos back using period \(2L\) to convert it to the actual coordinate within the corridor:
   • Take pos modulo 2L (handling negative numbers correctly).
   • If the resulting value exceeds \([0, L]\), fold it back again (\(2L - pos\)).

This allows us to determine the final position quickly and accurately.

Example

For example, with \(L = 5\), \(T = 7\), initial position \(x = 1\), velocity \(v = 2\): - Travel distance: \(2 \times 7 = 14\) - Tentative position: \(1 + 14 = 15\) - Modulo by period \(2L = 10\): \(15 \bmod 10 = 5\) - Still within range (\(5 = L\), so it’s OK) → Final position is \(5\)

Complexity

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

Since we perform constant-time computation for each robot, the overall solution runs in linear time.

Implementation Notes

• Don’t forget to implement the reflection handling at the initial state (velocity reversal at time 0).

• Be careful that the modulo operator % works correctly for negative numbers (Python’s % is safe in this regard).

• Note that if the corridor length is \(0\) (\(L = 0\)), all robots are always at coordinate \(0\).

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    N = int(data[idx]); idx += 1
    L = int(data[idx]); idx += 1
    T = int(data[idx]); idx += 1
    
    robots = []
    for _ in range(N):
        x = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        robots.append((x, v))
    
    result = []
    for x, v in robots:
        if v == 0:
            result.append(x)
            continue
        
        # 初期位置での反射処理
        if x == 0 and v < 0:
            v = -v
        elif x == L and v > 0:
            v = -v
        
        # 移動距離
        dist = abs(v) * T
        if v > 0:
            pos = x + dist
        else:
            pos = x - dist
        
        # 廊下の範囲 [0, L] で折り返す周期的性質を利用する
        # パターンの周期は 2*L
        period = 2 * L
        if period == 0:
            # L=0の場合、全ロボットは常に0にいる
            result.append(0)
            continue
            
        # pos を period で剰余を取る（ただし負の数にも対応）
        pos = pos % period
        
        # [0, L] の範囲内に収める
        if pos <= L:
            final_pos = pos
        else:
            final_pos = 2 * L - pos
            
        result.append(final_pos)
    
    print('\n'.join(map(str, result)))

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.