Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #51 C問題 - Pie or die (この記事を編集する[管理者用])

Source

Codeforces Beta Round #51 C問題
Problem description
Beta Round #51の自分の参加記録

問題概要

2人でゲームを行う.
n*mのグリッド上 (100*100以下) にK個 (100以下) のパイが置かれている.
先手は1個でもパイを盤面の外に出して手に入れたら勝ち.後手は先手がパイを手に入れれないと勝ち.
各ターン,先手は1つのパイを選んで上下左右に移動させることができる.
後手は,盤面の縁を1つ選んで,壁を作って,そこをパイを通れなくすることができる.
先手必勝か,後手必勝か,を判定する問題.
パイは同じセルに複数存在することができる.

解法

先手は,縁に一番近いパイを縁の周りをぐるぐる回していくのが最適.
後手は,一番端は1箇所で2箇所塞がないといけないので,4ターンの余裕があれば,全部塞げる.

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 main(){
  int i,j,k,l,m,n;
  int x,y,win;

  while( scanf("%d%d%d",&x,&y,&n)==3 ){
    win = 0;
    while(n--){
      scanf("%d%d",&i,&j);
      i--; j--;
      if(x-i-1 < i) i = x-i-1;
      if(y-j-1 < j) j = y-j-1;
      if(i<=4 || j<=4) win = 1;
    }
    if(win) puts("YES"); else puts("NO");
    break;
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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