Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 12427 - Donkey of the Sultan (この記事を編集する[管理者用])

Source

BUET Inter-University Programming Contest - 2011 (2012-02-18)
UVa 12427

問題概要

1次元上の半無限のグリッドがある.(左端は存在して,右端は存在しない)
2人でゲームをする.行動できなくなったら負け.自分は後手だけど,初期配置決めて良い.
勝てる初期配置の置き方のパターン数を求める問題.
最初,3枚のコインA, B, Cが置かれている.(左から順番に,コインA, B, C)
各ターン,1枚のコインを選び,それぞれ1マス左に移動させるか,コインAとCを同時に左に1マス移動させるか,のどちらかができる.
ただし,コインが重なったり,グリッドからはみ出してはいけない.
初期配置は,
 コインAは左端から,a1マス以上,a2マス以下の空きマスを挟んで置く.
 コインBはコインAから,b1マス以上,b2マス以下の空きマスを挟んで置く.
 コインCはコインBから,c1マス以上,c2マス以下の空きマスを挟んで置く.

解法

実験してみれば良い.
左端,コインA間の空きマスの数が偶数,かつ,コインBとコインCの間の空きマスの数が偶数なら勝てることがわかる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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