l*******m
发帖数: 1096 | 1 There are several pumpkins laid in a circle. Two witches, Ghosty and Slimy,
take turns to remove pumpkins away. Each time they can take 1 or 2
consecutive pumpkins (pumpkins considered to be consecutive only if they are
consecutive on the original circle). Whoever picks up the last pumpkin wins
. Ghosty makes the first move. Who is going to win with best possible moves:
Ghosty or Slimy? |
l*******m
发帖数: 1096 | |
c*******v
发帖数: 2599 | 3 发给我儿子了。He is in grade 3，LoL
Please post the answer later, or he will keep asking.
【在 l*******m 的大作中提到】
: 比码工的题好玩多了，花了周末大半天
|
l*******m
发帖数: 1096 | 4 目前还没有数学solution
【在 c*******v 的大作中提到】
: 发给我儿子了。He is in grade 3，LoL
: Please post the answer later, or he will keep asking.
|
s*i
发帖数: 5025 | |
g****t
发帖数: 31659 | 6 是不是先拿的赢？
【在 l*******m 的大作中提到】
: 目前还没有数学solution
|
l*******m
发帖数: 1096 | 7 1,2: 先拿的人赢
>2: 后拿的人应该赢
我的程序可以找到几十，再大就算不动了。cache也加了。主要是没有线性或者以下复
杂度的算法，如果找到了，也就证明了
主要问题是目前dynamic programming的states不高效。
【在 g****t 的大作中提到】
: 是不是先拿的赢？
|
l******n
发帖数: 9344 | 8 南瓜数量是3的倍数的时候第二个赢，因为第二个只需要每次根据第一个人拿的数量，
拿1或2凑成3的倍数，这样第二个就肯定赢。
其他时候都是第一个赢，策略就是南瓜数目是3k+m的时候先拿m，然后用上面的策略就
可以了。
这个算是线性吧
,
are
wins
moves:
【在 l*******m 的大作中提到】
: There are several pumpkins laid in a circle. Two witches, Ghosty and Slimy,
: take turns to remove pumpkins away. Each time they can take 1 or 2
: consecutive pumpkins (pumpkins considered to be consecutive only if they are
: consecutive on the original circle). Whoever picks up the last pumpkin wins
: . Ghosty makes the first move. Who is going to win with best possible moves:
: Ghosty or Slimy?
|
l*******m
发帖数: 1096 | 9 这个题有order限制，如果两个不相邻就拿不了
【在 l******n 的大作中提到】
: 南瓜数量是3的倍数的时候第二个赢，因为第二个只需要每次根据第一个人拿的数量，
: 拿1或2凑成3的倍数，这样第二个就肯定赢。
: 其他时候都是第一个赢，策略就是南瓜数目是3k+m的时候先拿m，然后用上面的策略就
: 可以了。
: 这个算是线性吧
:
: ,
: are
: wins
: moves:
|
p***o
发帖数: 1252 | 10 这个想法好，结论不对，3个及以上，第二个人都可以赢。
如果有2n个，n>=2
第一个人拿1,2，那么第二个人拿n+1,n+2
第一个人拿1，那么第二个人拿n+1
如果有2n+1个，n>=1
第一个人拿1,2，那么第二个人拿n+2
第一个人拿1，那么第二个人拿n+1,n+2
这样剩下的两部分按直径轴对称，往下第二个mirror play就好。 |
|
|
C*****l
发帖数: 1 | 11 这题要用上对称性，
如果是偶数个，180度两两对称，所以第二个人只要mirror play，肯定是他收官。
如果是奇数个，第一个人可以先拿走一个，反转成后手。
【在 l*******m 的大作中提到】
: 这个题有order限制，如果两个不相邻就拿不了
|
g****t
发帖数: 31659 | 12 这个是take turn拿。每个人都用自己预见的最佳策略。除了dp穷举。
这题都不一定是严格的。
Who is going to win with best possible moves
这个best possible moves should be defined with some measures/length/steps
in advance.
【在 p***o 的大作中提到】
: 这个想法好，结论不对，3个及以上，第二个人都可以赢。
: 如果有2n个，n>=2
: 第一个人拿1,2，那么第二个人拿n+1,n+2
: 第一个人拿1，那么第二个人拿n+1
: 如果有2n+1个，n>=1
: 第一个人拿1,2，那么第二个人拿n+2
: 第一个人拿1，那么第二个人拿n+1,n+2
: 这样剩下的两部分按直径轴对称，往下第二个mirror play就好。
|
l*******m
发帖数: 1096 | 13 楼上几位牛，谢谢。对，他们在讲even odd。对称！！！ |
s****a
发帖数: 1086 | 14 当轴线确定后，一方是可以拿跨轴线的两个相邻的的
【在 C*****l 的大作中提到】
: 这题要用上对称性，
: 如果是偶数个，180度两两对称，所以第二个人只要mirror play，肯定是他收官。
: 如果是奇数个，第一个人可以先拿走一个，反转成后手。
|
g****t
发帖数: 31659 | 15 best possible moves怎么解释的？
应该就是有一个人不管对方干什么都能赢吧。
【在 l*******m 的大作中提到】
: 楼上几位牛，谢谢。对，他们在讲even odd。对称！！！
|
p***o
发帖数: 1252 | 16 老顾你去网上搜搜nim game，变种策略证明多的很。
【在 g****t 的大作中提到】
: best possible moves怎么解释的？
: 应该就是有一个人不管对方干什么都能赢吧。
|
o**o
发帖数: 3964 | 17 3k+1 or 3k+2 sure win
3k sure lose, if the counterparty makes right moves |
f*******t
发帖数: 7549 | 18 怎么看都像码工的game theory类题。LC上有个stone game系列。
【在 l*******m 的大作中提到】
: 比码工的题好玩多了，花了周末大半天
|
l*******m
发帖数: 1096 | 19 对。这种镜像policy, 应该只是一种必赢策略。我的DP还有非镜像的，当然有可能可以
map到镜像的方案
【在 g****t 的大作中提到】
: best possible moves怎么解释的？
: 应该就是有一个人不管对方干什么都能赢吧。
|
l*******m
发帖数: 1096 | 20 西方数学教育比较注重归纳，递归教育。在这种教育下，比较聪明的的确不用怎么刷题
，因为太自然就想到了。
【在 f*******t 的大作中提到】
: 怎么看都像码工的game theory类题。LC上有个stone game系列。
|
|
|
g*****y
发帖数: 7271 | 21 偶数个的分析是对的，后拿的人稳赢。
奇数个的情况，第二个人在对称的地方拿2个，让剩下的情况重新偶数对称，就稳赢了。
所以只要多余2个，就是后拿的那人稳赢。
【在 C*****l 的大作中提到】
: 这题要用上对称性，
: 如果是偶数个，180度两两对称，所以第二个人只要mirror play，肯定是他收官。
: 如果是奇数个，第一个人可以先拿走一个，反转成后手。
|
f********g
发帖数: 45 | 22
正解，这题是小学三年级数奥里的圆桌上拿硬币那个题目的变种，是一道好题。
【在 p***o 的大作中提到】
: 这个想法好，结论不对，3个及以上，第二个人都可以赢。
: 如果有2n个，n>=2
: 第一个人拿1,2，那么第二个人拿n+1,n+2
: 第一个人拿1，那么第二个人拿n+1
: 如果有2n+1个，n>=1
: 第一个人拿1,2，那么第二个人拿n+2
: 第一个人拿1，那么第二个人拿n+1,n+2
: 这样剩下的两部分按直径轴对称，往下第二个mirror play就好。
|
d***a
发帖数: 13752 | 23 这个问题我小时候做过！不过好像是苹果或者桔子。
,
are
wins
moves:
【在 l*******m 的大作中提到】
: There are several pumpkins laid in a circle. Two witches, Ghosty and Slimy,
: take turns to remove pumpkins away. Each time they can take 1 or 2
: consecutive pumpkins (pumpkins considered to be consecutive only if they are
: consecutive on the original circle). Whoever picks up the last pumpkin wins
: . Ghosty makes the first move. Who is going to win with best possible moves:
: Ghosty or Slimy?
|
g****t
发帖数: 31659 | 24 你老不会是奥赛X牌吧……
: 这个问题我小时候做过！不过好像是苹果或者桔子。
: ,
: are
: wins
: moves:
【在 d***a 的大作中提到】
: 这个问题我小时候做过！不过好像是苹果或者桔子。
:
: ,
: are
: wins
: moves:
|
l**********3
发帖数: 10970 | 25 这题的难度是不需要连续的拿
你可以在一圈里面的任意地方开始拿 |
