// TODO: 解答不能のため, 以下のサイトを参考にした. // ニム(複数山の石取りゲーム)の必勝法. // https://mathtrain.jp/nim #include using namespace std; typedef long long LL; // n桁の0埋めの数字を作る. // https://gin0606.hatenablog.com/entry/2013/12/24/134138 // @param s: 0埋めしたい文字列(※d桁より多い場合は, 0埋め出来ないので何もしない). // @param d: 0埋め後の桁数. string fillText(string s, LL d) { string ret = s; while(ret.size() < d) ret = "0" + ret; return ret; } // Use of dynamic bitset to convert decimal numbers. // https://stackoverflow.com/questions/42759330/use-of-dynamic-bitset-to-convert-decimal-numbers // 10進数 → 2進数. // @param n: 2進数へ変換したい10進数. // @param d: 2進数表記する桁数. // @return: 2進数. string decimalToBinary(LL n, LL d) { if(n == 0) return fillText("0", d); string ret; LL ln = abs(n); while(ln) { ret = string((ln & 1) ? "1" : "0") + ret; ln /= 2; } ret = fillText(ret, d); if(n < 0) ret = "-" + ret; return ret; } int main() { // 1. 入力情報取得. LL N; cin >> N; // 2. ニムの必勝法??? // 1 ~ N までの 排他的論理和 を計算し, その各桁の mod 2 を保存. // ex. 15 までの排他的論理和の合計. // 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 // -> 8888 // // ex. 他のケースについての排他的論理和の合計. // 19 = 16 + 0 + 0 + 2 + 1 // = 18888 + 00000 + 00000 + 20011 + 10011 // = 4, 8, 8, 10, 10 // 27 = 16 + 8 + 0 + 2 + 1 // = 18888 + 81444 + 00000 + 22011 + 11011 // = 12, 12, 12, 14, 14 // 29 = 16 + 8 + 1 + 0 + 1 // = 18888 + 81444 + 44122 + 00000 + 11101 // = 14, 14, 14, 14, 15 // 2-1. N の 2進数表現取得(32桁). LL d = 0, DN = N; while(DN > 0) DN /= 2, d++; string nStr = decimalToBinary(N, d); // cout << "d=" << d << " nStr=" << nStr << endl; // 2-2. 2 の べき乗 を保存. LL pow2[d]; pow2[0] = 1; for(LL i = 1; i < d; i++) pow2[i] = 2 * pow2[i - 1]; // for(LL i = 0; i < d; i++) cout << "pow2[" << i << "]=" << pow2[i] << endl; // 2-3. N までの 排他的論理和 の 合計 に向けた準備. // ex. 29 ならば, nXorStock に, 以下の値を保存. // 1 8 8 8 8 // 8 1 4 4 4 // 4 4 1 2 2 // 0 0 0 0 0 // 1 1 1 0 1 LL nXorStock[d][d]; for(LL i = 0; i < d; i++){ int ci = nStr[i] - '0'; for(LL j = 0; j < d; j++){ int cj = nStr[j] - '0'; if(j < i) nXorStock[i][j] = (pow2[d - 1 - i]) * ci * cj; if(j == i) nXorStock[i][j] = 1 * ci; if(j > i) nXorStock[i][j] = (pow2[d - 1 - i] / 2) * ci; } } // for(LL i = 0; i < d; i++){ // for(LL j = 0; j < d; j++){ // cout << nXorStock[i][j] << " "; // } // cout << endl; // } // 2-4. N までの 排他的論理和 の 合計 を, 各桁ごとに取得. LL nXor[d]; for(LL i = 0; i < d; i++) nXor[i] = 0; for(LL j = 0; j < d; j++) for(LL i = 0; i < d; i++) nXor[j] += nXorStock[i][j]; // for(LL i = 0; i < d; i++) cout << nXor[i] << " "; // 3. 配列 nXor に, 奇数 が 含まれてなければ, 後手勝利と見る. string ans = "X"; for(LL i = 0; i < d; i++) if(nXor[i] % 2 == 1) ans = "O"; // 4. 後処理. cout << ans << endl; return 0; }