結果

問題 No.102 トランプを奪え
コンテスト
ユーザー codershifth
提出日時 2015-10-02 00:56:48
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 2,115 bytes
コンパイル時間 1,751 ms
コンパイル使用メモリ 173,564 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-19 19:02:13
合計ジャッジ時間 2,450 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;


class TakeTrump {
public:
    map<vector<int>,int> memo;
    int grundy(const vector<int>& n) {
            if (memo.count(n))
                return memo[n];
            set<int> S;
            auto N = n;
            REP(i,4)
            FOR(j,1,N[i]+1)
            {
                N[i] -= j;
                S.insert(grundy(N));
                N[i] += j;
            }
            int res = 0;
            while (S.count(res))
                ++res;
            return memo[n] = res;
    }
    void solve(void) {
            // 結局最後にトランプをとった方の勝ちになる。
            // 山がひとつだけのときを考えると
            //
            // 1~3 なら勝ち
            // 4 なら負け
            // 5 なら勝ち -> 4 へ遷移すればよい
            // 6 なら勝ち -> 4
            // 7 なら勝ち -> 4
            // 8 なら負け -> 5,6,7
            // 9 なら勝ち -> 8
            // 10 なら勝ち -> 8
            //  :
            // => 4 の倍数なら負け
            //
            // n 個の山があるとき
            // A が k (1<=k<=4) 個取るとき
            // B は 4-k 個取れば n-k-(4-k) = n-4 となり、 n%4 の結果は変わらない。
            // よって初期状態(で勝敗が決するなら)の山の高さは 0,1,2,3 と考えてよい。
            //
            // Nim として grandy 数を求めて解ける
            //
            vector<int> n(4);
            REP(i,4)
            {
                cin>>n[i];
                n[i] %= 4;
            }
            if (grundy(n))
                cout<<"Taro"<<endl;
            else
                cout<<"Jiro"<<endl;
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new TakeTrump();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0