组合数学取子游戏nim - CSDN文库

4星 · 超过85%的资源需积分: 15 188 浏览量更新于2023-06-14 评论收藏 19KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

nim

Time Limit:1000MS Memory Limit:65536K

Description

Nim is a 2-player game featuring several piles of stones. Players alternate turns, and on his/her

turn, a player’s move consists of removing one or more stones from any single pile. Play ends

when all the stones have been removed, at which point the last player to have moved is declared

the winner. Given a position in Nim, your task is to determine how many winning moves there are

in that position.

A position in Nim is called “losing” if the first player to move from that position would lose if

both sides played perfectly. A “winning move,” then, is a move that leaves the game in a losing

position. There is a famous theorem that classifies all losing positions. Suppose a Nim position

contains n piles having k1, k2, …, kn stones respectively; in such a position, there are k1 + k2 +

… + kn possible moves. We write each ki in binary (base 2). Then, the Nim position is losing if

and only if, among all the ki’s, there are an even number of 1’s in each digit position. In other

words, the Nim position is losing if and only if the xor of the ki’s is 0.

Consider the position with three piles given by k1 = 7, k2 = 11, and k3 = 13. In binary, these

values are as follows:

111

1011

1101

There are an odd number of 1’s among the rightmost digits, so this position is not losing.

However, suppose k3 were changed to be 12. Then, there would be exactly two 1’s in each digit

position, and thus, the Nim position would become losing. Since a winning move is any move that

leaves the game in a losing position, it follows that removing one stone from the third pile is a

winning move when k1 = 7, k2 = 11, and k3 = 13. In fact, there are exactly three winning moves

from this position: namely removing one stone from any of the three piles.

Input

The input test file will contain multiple test cases, each of which begins with a line indicating the

number of piles, 1 ≤ n ≤ 1000. On the next line, there are n positive integers, 1 ≤ ki ≤ 1, 000,

000, 000, indicating the number of stones in each pile. The end-of-file is marked by a test case

with n = 0 and should not be processed.

Output

For each test case, write a single line with an integer indicating the number of winning moves

from the given Nim position.

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余2页未读，立即下载

评论1

a1894233716

2013-10-06

这个代码真的有点少，有点简单，不过是能用

huangxinxe

粉丝: 0
资源: 3

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈