Alex 在和 Ball 玩游戏,他们面前有一个 n×nn \times nn×n 的空白矩阵 MMM,Alex 和 Ball 轮流往上放标记,Ball 先手。
矩阵中的一个格子被放置标记后就不能再放置标记,同时我们记 Alex 放的标记为 AAA 标记,Ball 放的标记为 BBB 标记。
在某一轮游戏结束后(一轮游戏指的是 Ball 先操作,然后 Alex 操作),若存在一个排列 p[1..n]p[1..n]p[1..n] 使得对任意 i∈[1,n]i \in [1,n]i∈[1,n],满足 M[i][p[i]]=AM[i][p[i]]=AM[i][p[i]]=A,则Alex立即获胜。
在 ⌊n2/2⌋\lfloor n^2 /2 \rfloor⌊n2/2⌋ 轮后,若 Alex 没有获胜,则 Ball 获胜。
若 Alex 或 Ball 在某个时刻做了非法的操作(由于遗忘在放过标记的地方重复放),他会直接输掉游戏。
狡猾的 Ball 想了一个办法来恶心 Alex ,他每隔很久很久才给出下一个操作,这样 Alex 可能会忘掉双方之前的操作。
现在你得到了这个信息,对于一个给定的 nnn,你想知道两件事:
- Alex 在自己每次操作前记得双方之前所有操作的情况下是否有必胜策略。
- Alex 在自己每次操作前忘掉双方之前所有操作,仅知道 Ball 最后一次操作的情况下是否有必胜策略。
Ball 永远记得双方的所有操作。
Alex is playing a game with Ball. There is a blank matrix MMM with nnn lines and nnn columns. Alex and Ball take turns to mark one of the matrix elements with his own sign (Alex’s sign is called AAA and Ball’s sign is called BBB). Ball goes first.
After a round of game (a round means that Ball and Alex operates once each in order), if there exists a permutation p[1..n]p[1..n]p[1..n] satisfies that for each i∈[1,n] i \in [1,n]i∈[1,n],M[i][p[i]]=AM[i][p[i]]=AM[i][p[i]]=A, Alex wins immediately.
After ⌊n2/2⌋\lfloor n^2 /2 \rfloor⌊n2/2⌋ rounds, if Alex hasn’t won, Ball wins instead.
Notice that whenever anyone tries to mark a marked matrix element(because of forgetting), he will lose the game immediately.
Sly Ball thinks of a way to interfere Alex. He decides to operate long time after the Alex’s last operation so that Alex may forget about the previous operations.
Now you get this message and want to know two things for a given nnn:
- whether Alex has winning strategy if he remembers all the previous operations
- whether Alex has winning strategy if he forgets all the previous operations, and only knows Ball's last operation each time.
Ball always knows all their previous operations.