Hatena::Grouptopcoder

Wrong Answer -- japlj このページをアンテナに追加 RSSフィード

 | 

2011-01-21

PKU 3537 -- Crosses and Crosses

| 16:56 | PKU 3537 -- Crosses and Crosses - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - PKU 3537 -- Crosses and Crosses - Wrong Answer -- japlj PKU 3537 -- Crosses and Crosses - Wrong Answer -- japlj のブックマークコメント

連続する n 個の空白からなる盤面に対するGrundy数を計算する。ある場所に x を書くと、そのxから距離が2以下のところに次に x を置くと確実に負けるので、x の両隣2マス分は除外して考えられる。


#include<cstdio>
#include<algorithm>

using namespace std;

int main()
{
  int n, grundy[2048] = {0};
  scanf("%d", &n);
  for(int i=1; i<=n; ++i) {
    int reach[2048] = {0};
    for(int j=0; j<i; ++j) reach[grundy[max(j-2,0)]^grundy[max(i-j-3,0)]]=1;
    while(reach[grundy[i]]) grundy[i]++;
  }
  printf("%d\n", grundy[n] ? 1 : 2);
  return 0;
}
 |