Flow Problem

시간 제한2초메모리 제한2048 MB

요약
2 x n 격자의 흐름 순환을 찾아 토큰을 왼쪽과 오른쪽 가장자리 밖으로 떨어뜨리는 인터랙티브 문제이다.
난이도

어려움10점 중 9점

유형
그래프, 시뮬레이션, 구현, 수학
정답자
아직 제출이 없습니다

문제

This is an interactive problem.

There is a 2×n2 \times n grid (2≤n≤10002 \leq n \leq 1000), where rows are numbered from 00 to 11, and columns are numbered from 00 to n−1n - 1. Each cell of the grid has flow in one of the four directions: up, down, left, or right. The flow directions in the grid form a continuous cycle, either clockwise or counterclockwise. Here is an example of the grid with clockwise-directed flow:

You are playing a two-round game. At the start of each round, a token is placed on some cell. You make moves, and before every move, you know the token's current position. The goal is to drop one token from the left side of the grid and drop another token from the right side. It does not matter which side is used in which round. The size of the grid and the direction of the flow are unknown, but are fixed in advance. They do not change between rounds.

There is a list of possible moves:

  1. Move the token to an adjacent cell to the left, right, or another row. If there is no such cell, the token falls from the grid.
  2. Wait for tt seconds (0≤t≤20020 \leq t \leq 2002). Each second, the token moves to an adjacent cell in the direction of the flow in the current cell.

Before each move, you are given the current coordinates of the token. You are allowed to use a limited number of moves. See details in the next section.

예제1

  1. 예제 1

    입력
    0 5
    
    no
    1 5
    
    no
    1 18
    
    no
    1 19
    
    yes
    1 2
    
    no
    0 2
    
    no
    0 1
    
    no
    0 0
    
    yes
    
    예상 출력
    
    wait 11
    
    
    wait 13
    
    
    right
    
    
    right
    
    
    switch
    
    
    left
    
    
    left
    
    
    left