class Solution {
public:
bool rec(map<int, bool> &cache, int n) {
if (n < 1) {
return false;
}
if (n <= 3) {
return true;
}

auto itr = cache.find(n % 3);
if (itr != cache.end()) {
return itr->second;
}

auto ret = !rec(cache, n - 1) || !rec(cache, n - 2) || !rec(cache, n - 3);
cache[n % 3] = ret;
return ret;
}
bool canWinNim(int n) {
map<int, bool> cache;
return rec(cache, n);
}
};


class Solution {
public:
bool canWinNim(int n) {
if (n <= 3) {
return true;
}
vector<int> dp(n + 1);
for (int i = 1; i <= 3; i++)
{
dp[i] = 1;
}

for (int i = 4; i <= n; i++) {
dp[i] = !dp[i - 1] || !dp[i - 2] || !dp[i - 3];
}
return dp[n];
}
};


dp[4] = 0
dp[5] = 1
dp[6] = 1
dp[7] = 1
dp[8] = 0
dp[9] = 1
dp[10] = 1
dp[11] = 1
dp[12] = 0
dp[13] = 1
dp[14] = 1
dp[15] = 1
dp[16] = 0
dp[17] = 1
dp[18] = 1
dp[19] = 1
dp[20] = 0
dp[21] = 1
dp[22] = 1
dp[23] = 1
dp[24] = 0
dp[25] = 1
dp[26] = 1
dp[27] = 1
dp[28] = 0
dp[29] = 1
dp[30] = 1
dp[31] = 1
dp[32] = 0
dp[33] = 1
dp[34] = 1
dp[35] = 1
dp[36] = 0
dp[37] = 1
dp[38] = 1
dp[39] = 1
dp[40] = 0
dp[41] = 1
dp[42] = 1
dp[43] = 1
dp[44] = 0
dp[45] = 1
dp[46] = 1
dp[47] = 1
dp[48] = 0
dp[49] = 1
dp[50] = 1
dp[51] = 1
dp[52] = 0
dp[53] = 1
dp[54] = 1
dp[55] = 1
dp[56] = 0
dp[57] = 1
dp[58] = 1
dp[59] = 1
dp[60] = 0
dp[61] = 1
dp[62] = 1
dp[63] = 1
dp[64] = 0
dp[65] = 1
dp[66] = 1
dp[67] = 1
dp[68] = 0
dp[69] = 1
dp[70] = 1
dp[71] = 1
dp[72] = 0
dp[73] = 1
dp[74] = 1
dp[75] = 1
dp[76] = 0
dp[77] = 1
dp[78] = 1
dp[79] = 1
dp[80] = 0
dp[81] = 1
dp[82] = 1
dp[83] = 1
dp[84] = 0
dp[85] = 1
dp[86] = 1
dp[87] = 1
dp[88] = 0
dp[89] = 1
dp[90] = 1
dp[91] = 1
dp[92] = 0
dp[93] = 1
dp[94] = 1
dp[95] = 1
dp[96] = 0
dp[97] = 1
dp[98] = 1
dp[99] = 1


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