Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SPOJ 1028 - Hubulullu [HUBULLU] (この記事を編集する[管理者用])

Source

Al-Khawarizm 2006
SPOJ 1028 [HUBULLU]

問題概要

2人でゲームをする.
1~nの数字が書かれた石がある.
毎ターン,残っている石を1つ選び,それに書かれた数字の約数が書かれた石を全部取り除く.
最後の石を取った人の勝ち.
nが与えられたとき,先手必勝か,後手必勝かを判定する問題.
nは1以上20億以下.

解法

どうみても先手必勝.
その証明は,例えば1の存在に着目するなど.
2~nだけが残されている状態で,勝てるなら,その通りにする.負けるなら1を取る.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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