読者です 読者をやめる 読者になる 読者になる

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

yukicoder No.102 トランプを奪え

問題

問題概要

省略

解法

grundy数とNimの勉強しました.

参考サイト

pekempey.hatenablog.com

d.hatena.ne.jp

上のサイトを参考にgrundy数を、1つの山について考えると、
残り枚数:0 1 2 3 4 5
grundy:0 1 2 3 0 1
のような関係になっている。 よって、n1,n2,n3,n4のやまそれぞれの数をmod4したもをxorすることで、勝敗がわかる。

ミス

grundy数理解したいね。使えるようにはなった気がする少しだけ。

コード

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)


int main(void){
    int n[4];
    rep(i, 4) cin >> n[i];
    int sum = 0;
    //残り枚数:0 1 2 3 4 5
    //grundy:0 1 2 3 0 1
    //残り枚数が4の時遷移先の最小のgrundyは1
    rep(i, 4){
        sum ^= n[i] % 4;
    }
    if(sum == 0)printf("Jiro\n");
    else printf("Taro\n");
}