首页 > 试题广场 >

翻硬币问题

[编程题]翻硬币问题
Alice和Bob正在玩一个很经典的游戏。
个硬币初始时全部正面朝上,每一轮Alice必须选择其中任意的恰好枚硬币并将它们全部翻转,如果若干轮翻转后所有硬币全部反面朝上,那么Alice就赢得了游戏。
假设我们认为每枚硬币只有正面朝上和反面朝上两种状态且只考虑为偶数的情况,问题会比较简单。
但是出题人希望这道题更毒瘤一些,所以他增加了一条规则:Bob在整个游戏中可以有一次机会使坏--在Alice某一轮翻转完之后,偷偷选择任意硬币并将它翻转。
为了不让Alice赢得游戏,Bob会采取最优的策略。
现在给定,请问Alice是否可以赢得游戏?
注意:
  1. Bob虽然可以在任何轮翻转之后使坏,但是在整个游戏中只有一次这样的机会。也就是说,如果在某一轮之后使用了这个机会,那么以后都不能再使用。
  2. 轮次可以认为是无限的,只要在任何一轮翻转后所有硬币全部反面朝上,Alice就立即赢得游戏胜利,Bob即使没有用掉使坏的机会也不能再偷偷翻转硬币。

输入描述:
每个输入文件有多个测试样例。
第一行一个整数--测试样例个数。
然后行,每行两个整数--硬币的数量和每一轮翻转硬币的数量。其中第行表示第个样例。


输出描述:
输出行,第行输出第个测试样例的答案。
如果Alice可以赢得游戏输出“Yes”,否则输出“No”,请注意区分大小写。
示例1

输入

2
2 2
8 6

输出

Yes
No

说明

对于第一个样例,Alice直接一轮翻转全部两个硬币就可以赢得游戏。

对于第二个样例,Bob如果在第一轮结束后将任意一枚反面朝上的硬币翻转,之后Alice无论怎样翻转硬币也永远不能使得所有硬币全部反面朝上。
头像 威风镰鼬
发表于 2021-11-06 16:12:21
思路 水题,m保证是偶数,那么Alice在剩下没翻硬币个数为奇数时永远也赢不了。 只要第一轮没有把硬币全部翻完,那么Bob就可以使坏让没翻的硬币数为奇, 也就是说,n和m不相等的情况下,永远是Bob赢。 代码 #include<bits/stdc++.h> using namespace 展开全文
头像 耕云种月
发表于 2022-01-25 21:17:16
原题解链接:https://ac.nowcoder.com/discuss/157310 因为mmm是一个偶数,不妨分类讨论: 1.一回合可以直接翻转所有硬币(n=m)(n=m)(n=m) 很显然,答案YesYesYes 2.一回合不能直接翻转所有硬币,因为mmm是偶数,所以只需要讨论nnn的奇偶性 展开全文