Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Language: A Coin Game
Description 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. Input 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. Output For each test case, if Sally can win the game, print “ Sample Input 0 4 1 1 1 2 2 1 2 2 1 1 1 1 2 2 Sample Output Yes T T T T Yes T Hint T is not explicitly given but is assumed to be large enough so that all involved squares lie in the board. Source POJ Monthly--2007.06.03, Yao, Jinyu |
[Submit] [Go Back] [Status] [Discuss]
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator