2003/Contest/マニラ大会

Problem A : Baby Huey's Coins and Trays

問題概要

円の内周に、別の円をいくつ並べられるか。

解法

数式の計算さえできれば、おそらくは今大会中最も易しい問題。


まず、

t = 外円の半径
c = 内円の半径

とする。

とりあえず、

t < c

ならば一つも並べられないのは明らか。

また、

c <= t < 2c

のときは一つだけ置くことができる。

その上で外円の中心と二つの隣り合う内円の中心を頂点とする三角形を考え、その中心角を元にいくつ並べられるかを考えればいい。つまり、

mikurube_A1.png

ここで、中心角 α を求めたい。

この二等辺三角形の半分を切り出すと以下のようになる。

mikurube_A2.png

よって

α = 2 arcsin(c / (t-c))

となる。

また、計算式がちょっと

2π/n <= α < 2π/(n+1)

のとき、 n (2 <= n) 個の内円を並べることができるので、最大の n は、

n = 2π/α = π/arcsin(c / (t-c))

とすることで求められる。


数式の計算で floor() で切り捨てる際、誤差が出る場合 (Sample Input) があったのでわずかな値を足してから floor() をかけている。大会中 (海津が回答) も同様の処理。 (三廻部)


自分はarcsinが使えない(笑)ので、

(t-c)sin(π/ans) > c

を越えない最大のansを答えとした。(A.java) (谷口)


Math.asin() ってのがあるみたいだけど...。 (三廻部)

議論・その他


ファイルを添付する

filetaniguchi_A.java 493件 [詳細] filemikurube_A2.mdrw 454件 [詳細] filemikurube_A2.png 524件 [詳細] filemikurube_A1.png 517件 [詳細] filemikurube_A1.mdrw 461件 [詳細] filemikurube_A.c 489件 [詳細]
[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

添付ファイル: filetaniguchi_A.java 493件 [詳細] filemikurube_A2.mdrw 454件 [詳細] filemikurube_A2.png 524件 [詳細] filemikurube_A1.png 517件 [詳細] filemikurube_A1.mdrw 461件 [詳細] filemikurube_A.c 489件 [詳細]

Last-modified: 2009-11-06 (金) 13:26:46 (2995d)