Overview

This is a problem where you move \(K\) times on \(N\) cells according to parity conditions based on the current cell number and the integer written on it, and you need to determine the destination after the moves. Since the number of moves \(K\) can be extremely large, you cannot solve this with simple simulation — instead, you need to exploit the regularity (cycles) in the movement pattern.

Analysis

1. Properties of Movement

The key characteristic of this problem is that “when you are on a given cell, the next cell you move to is uniquely determined.” The movement rules can be summarized as follows: - Cell \(1\): Move to cell \(2\) or stay at cell \(1\) depending on the condition - Cell \(i\) (\(2 \le i \le N-1\)): Move to cell \(i+1\) or \(i-1\) depending on the condition - Cell \(N\): Always stay at cell \(N\)

Once the destination is determined, you always move to the same place from the same cell. Therefore, if you return to a cell you have previously visited, from that point onward the same movement pattern repeats, forming a “cycle (period).”

2. The Size of \(K\) and Cycle Detection

The number of moves \(K\) can be as large as \(10^{18}\), so simulating one move at a time would not finish within the time limit. However, the total number of cells \(N\) is at most \(2 \times 10^5\). By the pigeonhole principle, after at most \(N+1\) moves, you are guaranteed to revisit a cell you have been to before.

Therefore, the problem can be solved efficiently with the following steps: 1. Perform the actual moves while recording “which cell was reached at which step.” 2. The moment you reach a cell that has already been visited, detect the cycle. 3. Use the remainder when dividing the remaining number of moves by the cycle length (modular arithmetic) to determine the final destination.

Algorithm

1. Preprocessing: For each cell \(i\), compute the next destination next_move[i] and store it in an array.
2. Simulation and Recording:
   • Set the current cell curr to \(1\), and prepare a list path to record the movement trajectory and an array visited_at to record the first visit step for each cell.
   • Repeat moves until either \(K\) moves are completed or a cycle is found.
3. Using the Cycle:
   • If at step \(s\) you reach a cell that was previously visited (visited at step \(m\)):
     • The cycle length is \(L = s - m\).
     • The state after \(K\) moves corresponds to the \((K - m) \pmod L\)-th element within the cycle.
4. Corner Cases: Be careful with output when \(N=1\) or when \(K\) moves are completed before entering a cycle.

Complexity

• Time Complexity: \(O(N)\)
  • Computing the next destination from each cell takes \(O(N)\), and simulating up to \(N+1\) moves for cycle detection also takes \(O(N)\), so the overall complexity is \(O(N)\).
• Space Complexity: \(O(N)\)
  • Arrays for storing next destinations and visit records use \(O(N)\) memory.

Implementation Notes

• 1-indexed vs 0-indexed: The cell numbers in the problem start from \(1\), but arrays in most programming languages start from \(0\), so be careful with index handling.

• Cycle Calculation: From the \(K\) total moves, subtract the number of moves \(m\) before entering the cycle, then compute the remainder when divided by the cycle length \(L\). In formula form, this looks like cycle[(K - m) % L].

  Source Code

import sys

# この問題は、すごろくの盤面上の移動が決定論的であり、マスの数が N 個であるため、
# K 回の移動の途中で必ず同じマスを再訪するか、特定のマスに留まることになります。
# K が非常に大きいため、周期性（サイクル）を検出することで効率的に解くことができます。

def solve():
    # 入力をすべて読み込み、スペースで分割します。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: マスの数, K: 移動回数
    N = int(input_data[0])
    K = int(input_data[1])
    # A: 各マスに書かれた整数
    A = list(map(int, input_data[2:]))

    # マスが1つしかない場合、常にマス1に留まります。
    if N == 1:
        print(1)
        return

    # 各マス i からの次の移動先をあらかじめ計算しておきます。
    # マス番号は1からNまでなので、サイズ N+1 の配列を使用します。
    next_move = [0] * (N + 1)
    
    # マス 1 の移動規則
    # A1 + A2 が偶数ならマス 2 へ、そうでなければマス 1 に留まる。
    if (A[0] + A[1]) % 2 == 0:
        next_move[1] = 2
    else:
        next_move[1] = 1
        
    # マス N の移動規則
    # 常にマス N に留まる。
    next_move[N] = N
    
    # マス 2 から N-1 までの移動規則
    # Ai + Ai+1 が偶数ならマス i+1 へ、そうでなければマス i-1 に戻る。
    for i in range(2, N):
        # A[i-1] はマス i の値、A[i] はマス i+1 の値に対応します。
        if (A[i-1] + A[i]) % 2 == 0:
            next_move[i] = i + 1
        else:
            next_move[i] = i - 1
    
    # 現在のマスを追跡し、サイクル検出を行います。
    curr = 1
    path = [curr]
    # visited_at[i] はマス i を最初に訪れた時のステップ数を記録します。
    visited_at = [-1] * (N + 1)
    visited_at[curr] = 0
    
    # 最大で N+1 回移動すれば、必ずサイクルに到達するか K 回の移動が終わります。
    for step in range(1, N + 2):
        # 指定された移動回数 K に達した場合は終了
        if step > K:
            break
        
        # 次のマスへ移動
        curr = next_move[curr]
        
        # 既に訪れたマスに到達した場合、サイクルを検出
        if visited_at[curr] != -1:
            # サイクルが始まったステップ
            m = visited_at[curr]
            # サイクルの構成要素を抽出
            cycle = path[m:]
            cycle_len = len(cycle)
            # K 回目の移動後のマスをサイクルの周期性から計算
            ans = cycle[(K - m) % cycle_len]
            print(ans)
            return
        
        # 訪問記録を更新
        visited_at[curr] = step
        path.append(curr)
    
    # K が小さく、サイクルを検出する前にシミュレーションが終了した場合
    if K < len(path):
        print(path[K])

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.