Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Round #102 DIV1 B問題/DIV2 D問題 - Help General (この記事を編集する[管理者用])

Source

Codeforces Round #102 DIV1 B問題 (1000pt)
Codeforces Round #102 DIV2 D問題 (2000pt)
Problem description

問題概要

n*m (1000*1000以下) のチェス盤を考える.
その上で,互いに攻撃できないようにナイトの駒を置くと,最大で何個置くことが出来るかを求める問題.

解法

対称性より,n ≤ mとする.
n=1の時は,全てに置けば良い.
n=2の時は,詰めておくことで,2*2において,次に2*2は置かない,とそれを繰り返すのが最適.
その他の時は,市松模様のように,行番号+列番号が2で割り切れる場所に置くと,ceil(n*m/2)個置ける.

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

  while(scanf("%d%d",&n,&m)==2){
    if(n > m) k = n, n = m, m = k;
    if(n==1){ printf("%d\n",m); continue; }
    if(n==2){
      k = (m/4) * 2;
      m %= 4;
      if(m > 2) m = 2;
      printf("%d\n",2*(k+m));
      continue;
    }

    res = (n*m+1)/2;
    printf("%d\n",res);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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