カメヲラボ

主にプログラミングとお勉強全般について書いてます

CodeIQ過去問集07:七夕問題☆牽牛 彦星 牛をもっと飼う

本稿はCodeIQで2014年7月7日~2014年7月28日に出題された「七夕問題☆牽牛 彦星 牛をもっと飼う」という問題を再編集したものです。 ※出題時と記述が一部異なる場合がありますがご了承ください。

七夕問題☆牽牛 彦星 牛をもっと飼う

【問題】

彦星はもっともっと天帝に認められ、お給料UPを目指しています。 そして織姫にプレゼントを買いたいのです。

さて、高価なプレゼントを狙う彦星は、今以上に仕事ぶりを天帝に認めてもらわなければなりません。 そこで彦星は、今までよりも破格にたくさんウシを育てることを決意しました。

ルールは、下記の通りです。

牛舎の大きさ一杯までウシを飼いたいところですが、一人で世話をしなければならないので、いくらか効率的に働かなければなりません。

彦星は、エサになる干し草を、牛舎の入り口からウシめがけて直接投げ入れ、エサをやる時間を短縮しようと考えました。

このように、格子状に彦星とウシが配置されます。彦星の位置が牛舎の入り口と考えてください。 ここから直接、ウシめがけてエサを投げます。 2×2のサイズの格子であれば、3頭すべてのウシにエサが届きます。 しかし、3×3の格子上に、目一杯ウシを配置すると、奥のウシにエサを届けることができません。 手前のウシに当たってしまうからです(天井が低いので、頭上を越えるように投げることはできません)。

すべてのウシにエサが届くようにウシを配置すると、次のように5頭のウシを飼うことができます。

エサを投げるとき、ウシに直撃さえしなければよいので、4×4のサイズなら、次のように9頭飼うことができます。

このようなルールでウシを飼うとすると、7777777 × 7777777のサイズの牛舎には最大何頭のウシを飼うことができるでしょうか?

【解説1】