frostar@wiki
CodeIQ:Scissors
最終更新:
frostar
-
view
- 問題概要
- 与えられた長方形に対し、コンパスで縦の長さと同じ正方形を描いていく。
- かけなくなったら最後の辺をはさみで切り、残った部分(正方形が描かれていない部分)を新たな長方形とし、同じ作業を繰り返す。
- 40回だけはさみを使う最小の長方形を見つける。
- ただし、長方形は縦の長さ<横の長さである。
- 解法
- 小さいほうから考えて、s回はさみを使うときの長方形を算出します。
- 長方形の大きさについて縦×横と表記することにします。
s=0の時の最小の長方形は1×1の正方形2個で構成された1×2の長方形です。
s=1の時の最小の長方形をn×mとするとn×nの正方形を切り取ってできる長方形が1×2になればよいと考えることができます。
n×mの長方形からn×nの正方形を切り取った後の長方形は縦がn、横がm-nの長方形です。
ただし、この時(m-n)<nであることから横が短い長方形になっているので、縦と横を入れ替えたn×(m-n)の長方形ができるといえます。
s=1の時の最小の長方形をn×mとするとn×nの正方形を切り取ってできる長方形が1×2になればよいと考えることができます。
n×mの長方形からn×nの正方形を切り取った後の長方形は縦がn、横がm-nの長方形です。
ただし、この時(m-n)<nであることから横が短い長方形になっているので、縦と横を入れ替えたn×(m-n)の長方形ができるといえます。
これを一般化すると
s回はさみを使って得られる長方形を(m-n)×nとすると、s+1回はさみを使って得られる最小の長方形はm×n
ここで、x=m-n、y=nとすると
s回はさみを使って得られる長方形をx×yとすると、s+1回はさみを使って得られる最小の長方形はx×(y+x)
s回はさみを使って得られる長方形を(m-n)×nとすると、s+1回はさみを使って得られる最小の長方形はm×n
ここで、x=m-n、y=nとすると
s回はさみを使って得られる長方形をx×yとすると、s+1回はさみを使って得られる最小の長方形はx×(y+x)
初期条件はs=0の時、x=1、y=2なので
これに対してs回y+xを繰り返せば正解が求まります。
ただし、x<yである必要があるため、1回の操作ごとにxとyの値を入れ替える必要があることに注意が必要です。
以上から作成したプログラムが以下の通りです。
ただし、x=width、y=heightです。
これに対してs回y+xを繰り返せば正解が求まります。
ただし、x<yである必要があるため、1回の操作ごとにxとyの値を入れ替える必要があることに注意が必要です。
以上から作成したプログラムが以下の通りです。
ただし、x=width、y=heightです。
public static void cut(int s){ int height = 1; int width = 2; for(int i=0;i<s;i++){ height+=width; int tmp = height; height = width; width = tmp; } System.out.println(height+"x"+width); }