Overview

This is a problem where you move \(K\) times on a board game (sugoroku) according to deterministic rules, and you need to find the number of the square you end up on. Since \(K\) can be as large as \(10^{18}\), a naive simulation is infeasible, so we use cycle detection to speed things up.

Analysis

Organizing the Movement Rules

The movement at each square \(i\) is determined solely by the parity of the sum of values of adjacent squares.

• Square \(N\): Always stays in place (goal)
• Square \(1\): If \(A_1 + A_2\) is even, move forward (to square \(2\)); if odd, stay
• Square \(i\) (\(2 \le i \le N-1\)): If \(A_i + A_{i+1}\) is even, move forward (to square \(i+1\)); if odd, move backward (to square \(i-1\))

A key observation is that the direction of movement at each square is determined solely by the values in array \(A\) and is always the same regardless of which step number it is. In other words, the state is completely determined by just “the current square number.”

Problem with Naive Simulation

Since \(K\) can be up to \(10^{18}\), simulating \(K\) moves one step at a time is far too slow (TLE).

Speeding Up with Cycle Detection

Since the state is one of the square numbers from \(1\) to \(N\), within at most \(N\) steps, the same square will be visited again. Returning to the same square means that from that point on, the exact same sequence of moves repeats (a cycle).

Concrete example: For \(N=5\), \(K=10^{18}\), if the movement history is \(1 \to 2 \to 3 \to 2 \to 3 \to 2 \to \cdots\), then at step 1 we’re at square 2, at step 2 we’re at square 3, and at step 3 we return to square 2. The cycle starts at step 1 with cycle length 2. By computing the remaining moves as \((K - 1) \mod 2\), we can determine the position within the cycle.

Algorithm

1. If \(N = 1\), the answer is \(1\).
2. Start the simulation from square \(1\).
3. At each step, record the “current square number” and check whether the same square number has appeared before.
4. If the same square is found (cycle detected):
   • Determine the cycle start step \(s\) and cycle length \(L\) (= current step \(- s\)).
   • Compute the remaining moves as \((K - s) \mod L\), and output the position at index \(s + ((K - s) \mod L)\) from the history.
5. If \(K\) steps of simulation finish before a cycle is found: Output the square number at that point.

Since there are at most \(N\) possible states, the cycle is detected within at most \(N + 1\) steps.

Complexity

• Time complexity: \(O(N)\) (the cycle is detected within at most \(N\) steps)
• Space complexity: \(O(N)\) (for storing the history and visit tracking)

Implementation Notes

• Parity check: The parity of \(A_i + A_{i+1}\) is determined solely by the parities of each \(A_i\). It can be checked with (A[i-1] + A[i]) % 2.

• 1-indexed vs 0-indexed conversion: In the problem statement, squares are 1-indexed, but since array \(A\) is stored as 0-indexed, the value at square \(i\) is A[i-1].

• Fixed points are also a type of cycle: When reaching square \(N\) and staying, or staying at square \(1\), these are naturally detected as cycles of length 1 (since the same square is recorded twice consecutively).

• When \(K\) is small: The \(K\) moves may finish before cycle detection occurs, so the upper bound of loop iterations is set to approximately \(\min(K, 2N+10)\).

  Source Code

import sys

def solve():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    A = list(map(int, input_data[2:2+N]))
    
    if N == 1:
        print(1)
        return
    
    # Precompute direction for each position (1-indexed)
    # For position i (1-indexed):
    #   i == N: stay at N
    #   i == 1: if (A[0]+A[1]) even -> go to 2, else stay at 1
    #   2 <= i <= N-1: if (A[i-1]+A[i]) even -> go to i+1, else go to i-1
    
    # Simulate but detect cycles
    # The position is bounded [1, N], and once we reach N we stay there.
    # Also, if at position 1 and direction is "stay", we stay forever.
    # Between positions 2..N-1, we either go forward or backward.
    # Key insight: movement is deterministic, so we can simulate and detect cycles.
    
    # But K can be up to 10^18, so we need cycle detection.
    # The state is just the current position (1 to N), so cycle length <= N.
    
    pos = 1  # 1-indexed
    
    # We'll simulate and track visited states to detect cycles
    # Since state space is at most N, cycle must occur within N steps
    
    history = []
    pos_to_step = {}
    
    for step in range(min(K, 2 * N + 10)):
        if pos in pos_to_step:
            # Found a cycle
            cycle_start = pos_to_step[pos]
            cycle_len = step - cycle_start
            remaining = (K - cycle_start) % cycle_len
            print(history[cycle_start + remaining])
            return
        pos_to_step[pos] = step
        history.append(pos)
        
        # Compute next position
        if pos == N:
            next_pos = N
        elif pos == 1:
            if (A[0] + A[1]) % 2 == 0:
                next_pos = 2
            else:
                next_pos = 1
        else:
            if (A[pos-1] + A[pos]) % 2 == 0:
                next_pos = pos + 1
            else:
                next_pos = pos - 1
        
        pos = next_pos
    
    # If no cycle detected within the simulation, we must have simulated enough
    # Or K was small enough
    if len(history) == K:
        # We did K steps of recording but haven't done the final move accounting
        # Actually history[i] = position after i moves (history[0] = position after 0 moves = start)
        # We need position after K moves = pos (which is the current position after the loop)
        print(pos)
    else:
        # Check if we ended up in a fixed point (pos == N or pos == 1 staying)
        # In that case pos_to_step would have caught it as a cycle of length 1
        # on the second visit. Let's just handle it:
        print(pos)

solve()

---

This editorial was generated by claude4.6opus-thinking.