|Online Judge||Problem Set||Authors||Online Contests||User|
A Coin Game
Harry and Sally have recently got addicted to a coin game. The game goes as follows.
The games uses a T × T grid board, each square in which is denoted by a pair of integers (x, y) between 1 and T (inclusive). Two players take turns to flip the coins. Each turn a player can choose four coins in the squares (x1, y1), (x1, y2), (x2, y1) and (x2, y2) (1 ≤ x1 < x2 ≤ T, 1 ≤ y1 < y2 ≤ T) to flip, as long as the coin in (x2, y2) will be turned from heads to tails. The player who cannot make a move loses.
After a sweet winning streak, Harry says to Sally, “Let’s have a bet! I’ll play first, and I’ll put heads in some squares and tails in some others of the board. You can decide whether the rest of coins shows heads or tails. I dare say you can’t beat me no matter how you put them.”
Given the squares in which Harry puts heads and those in which he puts tails, can you help Sally decide on the rest of coins so that she will win to teach the arrogant Harry a lesson? Assume that both Harry and Sally play optimally in the game.
The input contains multiple test cases. Each test cases begins with a line containing two integers n1 and n2 (n1, n2 ≤ 200). The next n1 + n2 lines each contain a pair of integers (x, y) (1 ≤ x, y ≤ 100). For the first n1 pairs, Harry puts heads in the corresponding squares. Harry lets Sally decide on coins in the squares denoted by the rest n2 pairs and puts tails in other squares.
For each test case, if Sally can win the game, print “
0 4 1 1 1 2 2 1 2 2 1 1 1 1 2 2
Yes T T T T Yes T
T is not explicitly given but is assumed to be large enough so that all involved squares lie in the board.
POJ Monthly--2007.06.03, Yao, Jinyu
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator