#P8144. Infinite Game on the Number Line

    ID: 21326 Type: Default 1000ms 256MiB

Infinite Game on the Number Line

Infinite Game on the Number Line

On a number line, there are 6 pieces placed at positions \(a_1, a_2, \ldots, a_6\) (with \(a_1 < a_2 < \cdots < a_6\)). Pieces 1, 2, 5, 6 are black and pieces 3, 4 are white.

Two players (black and white) play alternately. In each move, the player whose turn it is selects one of his pieces and moves it one step to the left or right. The following rules apply when moving:

  • If the destination contains pieces of the opponent color and there is exactly one such piece, then the moving piece may capture that opponent piece (i.e. remove it) and occupy the destination.
  • If the destination contains more than one opponent piece, the move is not allowed.
  • Any number of pieces of the same color can coexist at the same position.

The game ends when the current player has no legal moves; that player loses. Both players play optimally: each aims to force a win, and if a win is impossible, they try to force the game into an infinite loop (i.e. a draw) rather than lose.

Given which side moves first (either Black or White) and the initial positions of the 6 pieces, determine whether the game will continue indefinitely under optimal play. Print Yes if the game is forced to go on forever (i.e. a draw) and No if one side can force a win (thus ending the game in finite moves).

Notes:

  • The initial positions \(a_1, a_2, \dots, a_6\) are given in strictly increasing order.
  • Pieces are identified by their order: pieces 1, 2, 5, 6 are black; pieces 3, 4 are white.
  • Input and output details are given below.

inputFormat

The input consists of two lines:

  1. The first line contains a string, either Black or White, indicating which side moves first.
  2. The second line contains 6 space‐separated integers \(a_1, a_2, \ldots, a_6\) (with \(a_1 < a_2 < \cdots < a_6\)), representing the initial positions of the pieces.

outputFormat

Print a single line containing Yes if the game will continue indefinitely under optimal play, or No if one side can force the game to end in a win.

sample

Black
1 2 3 4 5 6
No