ガジェット通信

見たことのないものを見に行こう

第113回「今週のアルゴリズム:公平に分けられたケーキ2」正解者発表

DATE:
  • ガジェット通信を≫

「今週のアルゴリズム」とは

「今週のアルゴリズム」問題は、毎週火曜日にちょっとした問題を出題し、正解するとニックネームを掲載していくというシリーズ問題です。そして、正解した方全員に「たいへんよくできました」バッジも付与されます。

第113回は「今週のアルゴリズム:公平に分けられたケーキ2」の問題です。

問題文「第113回 今週のお題:公平に分けられたケーキ2」

ケーキを公平に分けるとき、太郎と次郎の2人がいる場合は以下の方法が有名です。

太郎がケーキを自分の価値観で公平であるように2つに分ける。
次郎が好きな方を選び、太郎は残りを取る。

今回は、太郎、次郎、三郎、…、m 郎の m 人で公平に切り分けることを考えます。
横幅が n の長方形のケーキを左から順に各自の価値観で垂直に切り、最後の人から逆順に好きな部分を選ぶものとします。

切ったケーキの横幅はいずれも整数になるものとします。
このとき、最大のケーキと最小のケーキの横幅の差が w 以下となるような切り方が何通りあるかを求めてください。

なお、ケーキを切らない選択も可能とします。
また、途中でケーキの幅が狭くなり切れなくなった場合は、そこで切るのをやめます。
最後の人から順に選ぶため、前半に切った人はケーキが割り当てられない場合があります。
このとき、ケーキの幅は 0 です。

例えば、m = 3, n = 5, w = 1 のとき、以下の図の左側にある3通りが考えられます。
右側のようなパターンは条件を満たさないため、不適切です。

標準入力から正の整数 m, n, w がスペースで区切って与えられます。
上記の条件を満たす切り方が何通りあるかを求め、標準出力に出力してください。
なお、m

【入出力サンプル】
標準入力
3 5 1

標準出力
3

正解者

おめでとうございます!正解者のみなさんです。(新着順)

angel様
rokusuke様
arbores様
えちごやえちぜん様
fourier様
swi様
mendmend様
distancedsilhouette様
gmk様
ほい様
i-don様
exaMG様
fukayanegi様
a992571様
toku-mori様
haruya様
choyotaura様
Chatnoir様
ベルファーレ長田様
鵜の右脳様
Yasu.Hara.様
se555様
ryagi様
noriok様
Mattsun様
nodoame2様
rw0020様
古典厩様
shooter1622様
14番様
facil89様
ゼロ式様
R修行中様
calc3様
kenj4様
おじけん様
hoi様
neko_the_shadow様
Q-system様
cia_rana様
Hira0404様
wx7890pack様
strauss様
神でなければ客ではない様
rotary-o様
dsk様
shoek様
scherzo2様
のみのみの様
todaemon様
Leopard551様
t5_____様
Pascal様
ゆん2様
piloswine様
Count0様
みかんず様
ばいおねす様
舞葉様
tnakao様
wand様
L.star様
chat様
pelicanlord様
smz8110様
Kilisame様
Azicore様
ciel様 

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。

TOP