#bYybttg060704. 1666:取石子游戏
1666:取石子游戏
好的,我将这道题整理为清晰的题面格式,并补充样例解释、数据范围与时空限制:
题目描述
原题来自:BeiJing 2009 WC
小 H 和小 Z 正在玩一个取石子游戏。取石子游戏的规则是这样的:
- 有 堆石子;
- 每个人每次可以从任意一堆石子中取出若干个石子;
- 每次取石子的个数必须是给定的集合 中的数;
- 谁不能取石子时就会输掉游戏。
小 H 先进行操作,他想问你他是否有必胜策略,如果有,第一步如何取石子(输出从哪堆取、取几个)。
输入格式
第一行为石子的堆数 。
接下来 行,每行一个数 ,表示第 堆石子的个数。
接下来一行为每次取石子个数的种类数 。
接下来 行,每行一个数 ,表示每次可以取的石子个数。
输入保证这 个数按照递增顺序排列。
输出格式
第一行为 YES 或者 NO,表示小 H 是否有必胜策略。
若结果为 YES,则第二行包含两个数,第一个数表示从哪堆石子取,第二个数表示取多少个石子。
若有多种答案,取第一个数(堆编号)最小的答案;若仍有多种答案,取第二个数(取的个数)最小的答案。
样例
样例输入
4
7
6
9
3
2
1
2
样例输出
YES
1 1
样例解释
石子堆数:,石子数量分别为 。
可取石子数的集合:,可取 或 个石子。
这是一个 限制取石子的 Nim 游戏(Nim with Restricted Move),可以用 SG 函数 来求解。
首先计算每堆石子的 SG 值:
- 对于一堆 个石子,每次可取 或 个:
- $SG(2)= \text{mex}\{SG(0), SG(1)\} = \text{mex}\{0,1\}=2$
- $SG(3)= \text{mex}\{SG(2), SG(1)\} = \text{mex}\{2,1\}=0$
- $SG(4)= \text{mex}\{SG(3), SG(2)\} = \text{mex}\{0,2\}=1$
- $SG(5)= \text{mex}\{SG(4), SG(3)\} = \text{mex}\{1,0\}=2$
- $SG(6)= \text{mex}\{SG(5), SG(4)\} = \text{mex}\{2,1\}=0$
- $SG(7)= \text{mex}\{SG(6), SG(5)\} = \text{mex}\{0,2\}=1$
- $SG(8)= \text{mex}\{SG(7), SG(6)\} = \text{mex}\{1,0\}=2$
- $SG(9)= \text{mex}\{SG(8), SG(7)\} = \text{mex}\{2,1\}=0$
因此:
- 堆1(7个):SG=1
- 堆2(6个):SG=0
- 堆3(9个):SG=0
- 堆4(3个):SG=0
初始 Nim-sum = ,先手必胜。
要找到第一步操作:
我们需要找到一堆石子,将其 SG 值从 变为 ,并且变化后石子数量减少的量是合法的(即可取集合 中某个数)。
这里 Nim-sum=1,所以我们要找一堆 对应的堆,且该堆减少石子后的 SG 值为 。
- 对于堆1(SG=1):,所以要从这堆石子中取若干石子,使其 SG 值从 1 变为 0。查表可知:石子数 7(SG=1)→ 变为石子数 6(SG=0),需要取 个石子。合法(可取集合中有 1)。
- 所以第一步:从第 1 堆取 1 个石子。
输出 YES 和 1 1。
数据范围
对于全部数据:
时空限制
- 时间:
- 内存:
提示
这是 有限取子游戏的组合(Take-away Game)的多堆版本。
解题步骤:
- 根据可取石子数集合 ,递推求出 到 的 SG 值;
- 计算初始所有堆 SG 值的异或和 ;
- 若 ,输出
NO;否则输出YES并找第一步; - 找第一步:枚举每一堆,尝试取 个石子,若取后该堆石子数合法(非负),且 ,且取后该堆的 SG 值等于 ,则找到一组解。按题意取堆编号最小、取的个数最小的方案。