Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2112-9d74d455
この記事にトラックバックする(FC2ブログユーザー)

Beta Round #73 DIV1 C問題/DIV2 E問題 - Interesting Game (この記事を編集する[管理者用])

Source

Codeforces Beta Round #73 DIV1 C問題 (1500pt)
Codeforces Beta Round #73 DIV2 E問題 (2500pt)
Problem description

問題概要

2人でゲームをする.動けなくなったら負け.
最初n個 (10^5以下) の石が1つの山に置いてある.
各ターン,1つの山を選び,それを2個以上の山に分割する.
そのとき,分割した各山の石の数は a, a+1, a+2, ..., a+k-1 個にならなければいけない.(aは任意の生成数,kは分割する山の数)
このゲームが先手必勝なら,最初に何個に分けると必勝か,それとも先手必敗かを求める問題.

解法

grundy numberを計算する.
山の数の取りうる値はそんなに多くないので,愚直に実装しても十分間に合う.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int grundy[100100], mini[100100];

int solve(int n){
  int i,j,k;
  int m;
  int up, down;
  int chk[1000];
  int fin = 0;

  if(grundy[n]>=0) return grundy[n];
  mini[n] = -1;

  rep(i,1000) chk[i]=0;

  for(k=2;;k++){
    up = 2*n - k*k + k;
    down = 2*k;

    if(up < down) break;
    if(up%down) continue;

    m = 0;
    up /= down;
    rep(i,k) m ^= solve(up+i);
    if(m<1000) chk[m] = 1;

    if(m==0 && fin==0) fin=1, mini[n] = k;
  }

  rep(i,1000) if(chk[i]==0) break;
  return grundy[n] = i;
}

int main(){
  int i,j,k,l,m,n;

  rep(i,100100) grundy[i] = -1;

  while(scanf("%d",&n)==1){
    solve(n);
    printf("%d\n",mini[n]);
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2112-9d74d455
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。