问题 D: SG函数

问题 D: SG函数

时间限制: 1 Sec  内存限制: 128 MB
提交: 196  解决: 114
[状态] [讨论版] [提交] [命题人:]
题目描述

博弈论 ,是经济学的一个分支,主要研究具有竞争或对抗性质的对象,在一定规则下产生的各种行为。博弈论考虑游戏中的个体的预测行为和实际行为,并研究它们的优化策略。

通俗地讲,博弈论主要研究的是:在一个游戏中,进行游戏的多位玩家的策略。

说起acm竞赛中的博弈论,就不得不提起SG函数和SG定理,下面给出SG函数和SG定理的定义。

SG定理:游戏和的SG函数等于各个游戏SG函数的Nim和。这样就可以将每一个子游戏分而治之,从而简化了问题。而Bouton定理就是SG定理在Nim游戏中的直接应用,因为单堆的Nim游戏 SG函数满足 SG(x) = x。

SG函数:先定义mex运算,这是施加于一个集合的运算,表最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。对于任意状态 x , 定义 SG(x) = mex(S),其中S是x的后续状态的SG函数值的集合。

相信经过上面的介绍学弟学妹们已经完全了解了博弈论的相关内容,现在写道题来练一下吧。

Alice和Bob在玩一个游戏:游戏开始时在一个长为n,宽为m的网格左上角格子内放置一枚棋子,两人轮流移动棋子,棋子每次仅能向下或向右移动一格,棋子不能移出边界,当某位玩家无法对棋子进行移动时,该玩家输掉游戏,假设Alice和Bob都绝顶聪明,两人都会做出当前局面下的最优选择,则两人谁会取得胜利。

对于每局游戏,Alice先移动棋子。

输入

多实例,先输入一个正整数t,表示测试实例数量,对于每组测试实例,输入两个正整数n和m (1<=n,m<=100000),分别代表网格的长和宽。 

保证实例数不大于200

输出

对于每组测试实例,如果Ailce获胜,输出”first win”,否则输出”second win”

样例输入 Copy
2
2 3
2 2
样例输出 Copy
first win
second win