73 lines
2.5 KiB
C++
73 lines
2.5 KiB
C++
// Source : https://leetcode.com/problems/nim-game/
|
|
// Author : Calinescu Valentin
|
|
// Date : 2015-10-19
|
|
|
|
/***************************************************************************************
|
|
*
|
|
* You are playing the following Nim Game with your friend: There is a heap of stones
|
|
* on the table, each time one of you take turns to remove 1 to 3 stones. The one who
|
|
* removes the last stone will be the winner. You will take the first turn to remove
|
|
* the stones.
|
|
*
|
|
* Both of you are very clever and have optimal strategies for the game. Write a
|
|
* function to determine whether you can win the game given the number of stones in the
|
|
* heap.
|
|
*
|
|
* For example, if there are 4 stones in the heap, then you will never win the game: no
|
|
* matter 1, 2, or 3 stones you remove, the last stone will always be removed by your
|
|
* friend.
|
|
*
|
|
* If there are 5 stones in the heap, could you figure out a way to remove the stones
|
|
* such that you will always be the winner?
|
|
*
|
|
* Credits:Special thanks to @jianchao.li.fighter for adding this problem and creating
|
|
* all test cases.
|
|
*
|
|
***************************************************************************************/
|
|
|
|
|
|
|
|
/*
|
|
* Solutions
|
|
* =========
|
|
*
|
|
* Let's look at the example:
|
|
*
|
|
* 0 stones - false
|
|
* 1 stone - true
|
|
* 2 stones - true
|
|
* 3 stones - true
|
|
* 4 stones - false
|
|
*
|
|
* We notice that all we need for a position to be true is to get the opponent in a position
|
|
* that is false. With 1, 2 and 3 you can take 1, 2 and 3 stones respectively to force your
|
|
* opponent into having 0 stones, a position where he cannot win. No matter how many stones
|
|
* we take from 4 we cannot
|
|
*
|
|
* force the opponent into a losing positon, so position 4 becomes a losing position.
|
|
* Let's take a look at the next 4 positions:
|
|
*
|
|
* 5 stones - true
|
|
* 6 stones - true
|
|
* 7 stones - true
|
|
* 8 stones - false
|
|
*
|
|
* With 5, 6 and 7 stones we can take 1, 2 and 3 stones respectively to force the opponent into
|
|
* position 4. Position 8 is a losing one because we can only force the opponent into winning
|
|
* positions. We notice that this group of 4 positions can repeat itself indefinitely, because
|
|
* we only need the previous 3 positions to judge whether a position is winning or losing.
|
|
*
|
|
* Thus we can see the pattern:
|
|
*
|
|
* n % 4 == 0 - false
|
|
* n % 4 != 0 - true
|
|
*
|
|
*/
|
|
|
|
class Solution {
|
|
public:
|
|
bool canWinNim(int n) {
|
|
return !(n % 4 == 0);
|
|
}
|
|
};
|