Chess Practice
Time limit2sMemory limit128 MB
Given N queens on a board, players alternately shift a queen toward (0,0) using Wythoff-move rules, and the winner is decided by XOR-ing Grundy values via Sprague-Grundy theory.
- Level
Hard8 of 10
- Topics
- Game theory, Dynamic programming, Math
- Solved
- No attempts yet
Problem
Sejun and Dasom enjoy playing chess as a hobby. Now they are training with the goal of joining the national team. Today they practice attacking techniques using only queens on a 100 by 100 chessboard.
There are N queens on the board. Sejun moves first, then Dasom, and they continue alternating turns.
On one turn, the player chooses one queen and moves it. If the queen is at (x, y), the player may choose a positive integer k and move it to one of (x-k, y), (x, y-k), or (x-k, y-k). A queen may pass through squares occupied by other queens, and multiple queens may occupy the same square.
The first player to place any queen on (0, 0) wins. Assuming both players play optimally, determine the winner of each game.
Input
The input contains 5 games. Each game has the following format.
The first line contains N, the number of queens on the board. N is at most 50. Each of the next N lines contains a queen position X Y. No queen is initially at (0, 0).
Output
For each game, print S if Sejun wins, or D if Dasom wins, one result per line.