题解与讨论区 1153: 张老师和石头的BattleII

题解与讨论区 1153: 张老师和石头的BattleII

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

返回问题页面

题目描述

 这一天菜哭武来到A国旅游,他的好朋友张老师和石头想带他到处逛逛。
 这个国家有n个城市和n-1条道路,从首都(编号为1)出发通过这些道路可以到达A国的任意一个城市。
 这n个城市中有k个城市有码头,每个码头都有足够多的渡船。一艘船刚好可以坐三个人,只需花费一张船票他们就能一起乘船回到首都。
 张老师手上有a张船票, 石头手上有b张船票。于是他们想玩一个游戏。游戏规则是这样的:
 他们三个人一开始都在首都,张老师和石头轮流决定他们接下来要怎么走,张老师先做决定。每次决定要么一起沿着道路走到下一个城市,要么花费自己手上的一张船票一起回到首都(前提是他们所在的城市有码头)。沿着道路走时,方向必须从离首都近的城市走向离首都远的城市。两个人轮流做决定,直到其中一个人无法继续做出决定(也就是不存在方法让他们继续移动),那么这个人就输了。菜哭武想知道最后谁会获胜。

第1153题的题解