Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SPOJ 9935 - Break the Chocolate [BC] (この記事を編集する[管理者用])

Source

ACM/ICPC Regional Contest, Chengdu 2011
SPOJ 9935 [BC]

問題概要

縦横高さがN*M*K (2000*2000*2000以下) のサイズのチョコレートがある.
これを1*1*1のチョコレートに切りたい.
方法1と方法2,それぞれで切るのに必要な最小回数を求める問題.
方法1は手で割る方法で,1回で1切れのチョコレートを好きな場所で2つに割ることができる.
方法2はナイフを使う方法で,1回で,好きな数のチョコレートの破片を一度に,それぞれ好きな場所で2つに切ることができる.

解法

手で割る場合,1回で一切れしか増えないので,答えはN*M*K-1.
ナイフを使う場合,2切れになったら,同じように同時に切れば良いので,二切れのうち大きい方のみになったと思えば良い.
大きい方のみに依存するから,できるだけ均等にしたほうが良いので,N, M, Kそれぞれに対して,N → ceil(N/2)という操作を1になるまでやる.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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