Game on Chessboard
Time limit1sMemory limit128 MB
Given K (p,q)-leapers on an M x N board, decide which player wins the disjunctive sum of impartial games.
- Level
Medium7 of 10
- Topics
- Game theory, Math
- Solved
- No attempts yet
Problem
You are given an chessboard. On it sit fairy chess pieces called -leapers (with ). Squares are addressed by (row, column), with rows numbered to from top to bottom and columns numbered to from left to right. Several leapers may occupy the same square.
A -leaper standing on square can move to any of the following four squares that lie on the board:
In each move the piece steps squares along one axis and squares along the other, and the length- step always points toward a smaller coordinate (upward in rows or leftward in columns). A move that would leave the board is forbidden.
Two players move alternately. On a turn, a player selects one leaper and moves it according to the rules above. The player who has no legal move on their turn loses. Assuming both players play optimally, determine who wins.
Input
The first line contains five integers , , , , (, , ).
Each of the next lines contains two integers and , the position of the -th leaper (, ).
Output
Print First if the player who moves first wins under optimal play, and Second otherwise.