#P8144. Infinite Game on the Number Line
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:
- The first line contains a string, either
Black
orWhite
, indicating which side moves first. - 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