Under construction

Still being built. Things may change

Flow Problem

Time limit2sMemory limit2048 MB

Summary
Given a 2 x n grid with a cyclic flow of unknown direction, find a sequence of moves that drops a token from the left and from the right within the move limit.
Level

Medium7 of 10

Topics
Simulation, Implementation, Game theory
Solved
No attempts yet

Problem

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. The figure below shows a grid with clockwise 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 they are fixed in advance and do not change between rounds.

You can make the following moves.

  1. Move the token to an adjacent cell to the left, right, or in the other 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 the adjacent cell in the direction of the flow in its current cell.

Before each move, you are given the current coordinates of the token. The number of moves you can use is limited. See the details in the next section.

Examples1

  1. Example 1

    Input
    0 5
    
    no
    1 5
    
    no
    1 18
    
    no
    1 19
    
    yes
    1 2
    
    no
    0 2
    
    no
    0 1
    
    no
    0 0
    
    yes
    
    Expected output
    
    wait 11
    
    
    wait 13
    
    
    right
    
    
    right
    
    
    switch
    
    
    left
    
    
    left
    
    
    left