yukicoder No.102 トランプを奪え
問題概要
省略
解法
grundy数とNimの勉強しました.
参考サイト
上のサイトを参考に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"); }