Nim博弈

Crazy Calendar(LightOJ-1393) 题面 2011 was a crazy year. Many people all over the world proposed on 11-11-11, married on 11-11-11, some even went through surgery only to have 11-11-11 as their child’s birth date. How crazy people can be! Don’t they see there is a “20” hidden? Then what to do? A very elegant solution came from ARR, a very famous and funny character - why do we need to follow Christian (or some calls it Gregorian) calendar? Why don’t we start our own calendar on the day of marriage? And those who like to celebrate their marriage ceremony too frequent, why don’t they declare only 1 day per year. In that fashion they can celebrate their anniversary every day. And may be one minute a year or a second or … Uh.. getting complex. Let’s back to the title. From now, we start to have a new calendar system, “Kisu Pari Na”. And we hope to update this calendar on every national contest. ...

Matrix Game(LightOJ-1247) 题面 Given an m x n matrix, where m denotes the number of rows and n denotes the number of columns and in each cell a pile of stones is given. For example, let there be a 2 x 3 matrix, and the piles are 2 3 8 5 2 7 That means that in cell(1, 1) there is a pile with 2 stones, in cell(1, 2) there is a pile with 3 stones and so on. ...

Left Right(LightOJ-1192) 题面 Two players, Alice and Bob are playing a strange game in a 1 x n board. The cells are numbered from 0 to n-1, where the left most cell is marked as cell 0. Each cell can contain at most one piece. There are two kinds of pieces, gray and white. Alice moves all the gray pieces, and bob moves all the white ones. The pieces alternate, that is, leftmost piece is gray, next is white, next to that is gray, then it’s white again, and so on. There will always be equal number of black and gray pieces. Alice can only move pieces to the right. Bob can only move pieces to the left. ...

Incredible Chess(LightOJ-1186) 题面 You are given an n x n chess board. Only pawn is used in the ‘Incredible Chess’ and they can move forward or backward. In each column there are two pawns, one white and one black. White pawns are placed in the lower part of the board and the black pawns are placed in the upper part of the board. The game is played by two players. Initially a board configuration is given. One player uses white pieces while the other uses black. In each move, a player can move a pawn of his piece, which can go forward or backward any positive integer steps, but it cannot jump over any piece. White gives the first move. ...

Nim(POJ-2975) 题面 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: ...

Georgia and Bob(POJ-1704) 题面 Georgia and Bob decide to play a self-invented game. They draw a row of grids on paper, number the grids from left to right by 1, 2, 3, …, and place N chessmen on different grids, as shown in the following figure for example: Georgia and Bob move the chessmen in turn. Every time a player will choose a chessman, and move it to the left without going over any other chessmen or across the left edge. The player can freely choose number of steps the chessman moves, with the constraint that the chessman must be moved at least ONE step and one grid can at most contains ONE single chessman. The player who cannot make a move loses the game. ...

Rabbit and Grass(HDU-1849) 题面 大学时光是浪漫的，女生是浪漫的，圣诞更是浪漫的，但是Rabbit和Grass这两个大学女生在今年的圣诞节却表现得一点都不浪漫：不去逛商场，不去逛公园，不去和AC男约会，两个人竟然猫在寝食下棋…… 说是下棋，其实只是一个简单的小游戏而已，游戏的规则是这样的： 1、棋盘包含1*n个方格，方格从左到右分别编号为0，1，2，…，n-1； 2、m个棋子放在棋盘的方格上，方格可以为空，也可以放多于一个的棋子； 3、双方轮流走棋； 4、每一步可以选择任意一个棋子向左移动到任意的位置（可以多个棋子位于同一个方格），当然，任何棋子不能超出棋盘边界； 5、如果所有的棋子都位于最左边（即编号为0的位置），则游戏结束，并且规定最后走棋的一方为胜者。 ...

Being a Good Boy in Spring Festival(HDU-1805) 题面 一年在外 父母时刻牵挂 春节回家 你能做几天好孩子吗 寒假里尝试做做下面的事情吧 陪妈妈逛一次菜场 悄悄给爸爸买个小礼物 主动地 强烈地 要求洗一次碗 某一天早起 给爸妈用心地做回早餐 ...

Matches Game(POJ-2234) 题面 Here is a simple game. In this game, there are several piles of matches and two players. The two player play in turn. In each turn, one can choose a pile and take away arbitrary number of matches from the pile (Of course the number of matches, which is taken away, cannot be zero and cannot be larger than the number of matches in the chosen pile). If after a player’s turn, there is no match left, the player is the winner. Suppose that the two players are all very clear. Your job is to tell whether the player who plays first can win the game or not. ...

Nim博弈 基本的尼姆博弈（Nim Game）描述如下： 有若干堆各若干个物品，两个人轮流从某一堆取任意多的物品，每次至少取一个，多者不限，最后取光者得胜。 博弈过程如下： ...