Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Croc Champ 2012 Round 2 C問題 - Playing with Superglue (この記事を編集する[管理者用])

Source

Croc Champ 2012 Round 2 C問題 (1500pt)
Problem description

問題概要

2人でゲームを行う.先手必勝か後手必勝かを判定する問題.
n*m (100*100以下) の盤面の上に2つの駒がある.
2つの駒の初期座標が与えられる.最初駒の位置は異なり,盤面は糊が付着していない.
各ターン,以下のことを行う.
 先手は,糊付けされていない駒を1つ選び,上下左右のどこかに1マスだけ動かす.
 後手は,まだ糊が塗られていない,かつ,駒が存在しないマスを1マス選び,糊を塗る.
糊が塗られているマスに駒が移動すると,糊付けされて動けなくなる.
2つの駒が同じマスに存在する状況になったらその時点で先手の勝ち.
そうでなく,2つの駒が両方糊付けされて動けなくなったら後手の負け.
勝敗が決る前に両者ともvalidな行動ができなくなることはないことは少し考えればわかる.

解法

初期の駒のx座標の差と,y座標の差のみによってかわる.
後手は,厚さ2の壁を作れれば必勝で,それは,x座標の差とy座標の差のうち,どちらかか5以上ならできる.
そうでないときは,難しいが,パターンが少ないので,それぞれ実際に色々考えてみると,x座標差とy座標差の和が6以下なら先手が勝てることがわかる.

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

int ab(int a){if(a<0)return -a; return a;}

int main(){
  int i,j,k,l,m,n;
  int x, y, x1, x2, y1, y2;
  int dx, dy;

  scanf("%d%d%d%d%d%d",&x,&y,&x1,&y1,&x2,&y2);

  dx = ab(x1-x2);
  dy = ab(y1-y2);

  if(dx <= 4 && dy <= 4 && dx+dy <= 6) puts("First");
  else puts("Second");

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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