結果
問題 | No.153 石の山 |
ユーザー |
|
提出日時 | 2019-10-28 23:44:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 1,355 bytes |
コンパイル時間 | 1,664 ms |
コンパイル使用メモリ | 166,568 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-14 21:21:39 |
合計ジャッジ時間 | 2,659 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))#define INF 2e9#define INF_LL 1LL<<60#define ll long longtypedef pair<ll, ll> P;int nim[101];/* nim[i]: 石がi個ある状態でのgrundy数 */int main(){int n; cin >> n;nim[2] = 1;REPN(i, 3, n+1) {int a=0, b=0;if(i % 2 == 0) {a = nim[i/2]^nim[i/2];} else {a = nim[(i+1)/2];a ^= nim[(i-1)/2];}if(i % 3 == 0) {b = nim[i/3]^nim[i/3]^nim[i/3];} else if (i % 3 == 1) {b = nim[(i-1)/3]^nim[(i-1)/3];b ^= nim[(i+2)/3];} else {b = nim[(i-2)/3];b ^= nim[(i+1)/3]^nim[(i+1)/3];}if(b < a) {int tmp = b;b = a;a = tmp;}REP(j, b+2) {if(j != a && j != b) {nim[i] = j;break;}}}if(nim[n] == 0) {cout << "B" << endl;} else {cout << "A" << endl;}return 0;}