跳转至

292.nim-game

Statement

Metadata
  • Link: Nim 游戏
  • Difficulty: Easy
  • Tag: 脑筋急转弯 数学 博弈

你和你的朋友，两个人一起玩 Nim 游戏：

  • 桌子上有一堆石头。
  • 你们轮流进行自己的回合， 你作为先手 。
  • 每一回合，轮到的人拿掉 1 - 3 块石头。
  • 拿掉最后一块石头的人就是获胜者。

假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。

 

示例 1：

输入：n = 4
输出：false 
解释：以下是可能的结果:
1. 移除1颗石头。你的朋友移走了3块石头，包括最后一块。你的朋友赢了。
2. 移除2个石子。你的朋友移走2块石头，包括最后一块。你的朋友赢了。
3.你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。
在所有结果中，你的朋友是赢家。

示例 2：

输入：n = 1
输出：true

示例 3：

输入：n = 2
输出：true

 

提示：

  • 1 <= n <= 231 - 1

Metadata
  • Link: Nim Game
  • Difficulty: Easy
  • Tag: Brainteaser Math Game Theory

You are playing the following Nim Game with your friend:

  • Initially, there is a heap of stones on the table.
  • You and your friend will alternate taking turns, and you go first.
  • On each turn, the person whose turn it is will remove 1 to 3 stones from the heap.
  • The one who removes the last stone is the winner.

Given n, the number of stones in the heap, return true if you can win the game assuming both you and your friend play optimally, otherwise return false.

 

Example 1:

Input: n = 4
Output: false
Explanation: These are the possible outcomes:
1. You remove 1 stone. Your friend removes 3 stones, including the last stone. Your friend wins.
2. You remove 2 stones. Your friend removes 2 stones, including the last stone. Your friend wins.
3. You remove 3 stones. Your friend removes the last stone. Your friend wins.
In all outcomes, your friend wins.

Example 2:

Input: n = 1
Output: true

Example 3:

Input: n = 2
Output: true

 

Constraints:

  • 1 <= n <= 231 - 1

Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll mod = 1e9 + 7;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
    return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
    return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

class Solution {
public:
    bool canWinNim(int n) {
        return (n % 4 != 0);
    }
};

#ifdef LOCAL

int main() {
    return 0;
}

#endif
最后更新: October 11, 2023
回到页面顶部