packing1 - 半導体工場 (Packing) Editorial /

Time Limit: 1 sec / Memory Limit: 64 MiB

AtCoder での提出方法

この提出先はテストケース 01 用です.このテストケースに対する出力ファイルを,言語 Text (cat) を選択して提出してください.

各テストケースの提出先: 01 | 02 | 03 | 04 | 05

AtCoder では,各入力に対応する 5 つの提出先に個別に提出する.相対評価に用いる最大スコアは,データ番号順に 0.18767886, 0.13896315, 0.11200462, 0.10566336, 0.05263157 である.これらより良いスコアでも各提出先の上限は 20 点である.第 1, 2, 3, 5 データの値は当時の生徒の最大スコア,第 4 データの値は当時のチューター解のうちの最良のものである.

配点 : 20 点

問題文

あなたの勤めている半導体工場では,最新鋭の装置を用いてシリコン板を加工し,半導体チップの材料として出荷している.シリコン板の加工に用いる装置は極めて高精度であり,加工位置を 10 ナノメートル単位で調整することができる(10 ナノメートル = 100{,}000{,}000 分の 1 メートル).

ある顧客からの注文により,あなたは,辺の長さが 1 メートルの正方形のシリコン板から,n 枚のシリコン円板を切り抜くことになった.切り抜くシリコン円板は全て同じ大きさでなければならない.また,貴重なシリコン板を無駄にしないよう,できるだけ大きい円板を切り抜くことが望ましい.

正方形のシリコン板から,できるだけ大きな n 枚のシリコン円板を切り抜く方法を求めよ.

入力

以下の表の n の値を,入力として用いよ.

データ番号 シリコン円板の枚数 n
1 6
2 11
3 17
4 22
5 90

出力

出力データをファイルとして提出せよ.出力データの作成方法は問わない.プログラムに直接生成させてもよいし,必要に応じて,それをテキストエディタ等で加工してもよい.出力データの作成に用いたプログラムを提出する必要は無い.

データ番号 k の入力に対する出力ファイル名は packing-outk.txt である(k = 1, 2, 3, 4, 5).

出力データは n 行からなる.n は切り抜くシリコン円板の枚数であり,入力の項で与えられている.i 行目 (1 \leqq i \leqq n) には,i 枚目のシリコン円板の中心の位置を表す 2 つの整数 x_i, y_i を空白を区切りとして出力せよ.これは,i 枚目のシリコン円板の中心が,正方形板の左端から x_i \times 10 ナノメートル,上端から y_i \times 10 ナノメートルの場所であることを意味する.x_i, y_i は 0 \leqq x_i, y_i \leqq 100{,}000{,}000 をみたす整数である.

切り抜くシリコン円板の大きさは,装置により自動的に計算されるので,出力データの中に書く必要はない.

モデル解法

この問題の一つの解法は次のようなものである.(m - 1)^2 < n \leqq m^2 をみたす整数 m を求める.正方形板を m \times m の小正方形板に分割する.そこから n 個の小正方形板を選び,内接する円板を切り抜く.これにより,半径 \frac{1}{2m} の円板を切り抜く解法が得られる.この解法を「モデル解法」と呼ぶことにする.モデル解法は必ずしも効率の良い解法ではない.

例 1

n = 3 の場合に,「モデル解法」によって得られた出力データは以下の通りである.

25000000 25000000
75000000 25000000
25000000 75000000

これを図示すると下図の通りである.

2007-packing-example1.png

例 2

例 1 は最適解ではない.例えば,

74540929 25404070
25474639 38662789
61538179 74593059

の方が良い結果を与える.これを図示すると以下の通りである.

2007-packing-example2.png

例 3

以下は,n = 8 の場合の出力データの例である.このデータは,「モデル解法」よりも良い結果を与える.

50993849 72645350
17399669 81993059
83110119 83073720
50245039 25147290
83063380 16879409
16948019 16965430
26471179 49375439
76212739 50011850

これを図示すると以下の通りである.

2007-packing-example3.png

採点について

出力データ毎に配点を定め,以下に従い,相対評価で採点を行う.

  • 出力データが誤っていた場合や未提出の場合は,その出力データに関する得点は 0 点である.また,半径が「モデル解法」以下の出力データも 0 点である.
  • 「モデル解法」よりも半径の大きなデータが提出された場合,その得点は次のようにして計算される.「モデル解法」の半径を d_0 とおく.提出された出力データの半径のうち,最も大きいものを d_1 (d_1 > d_0) とおく.半径 d (d_1 \geqq d \geqq d_0) の出力データには,配点のうち,\left(\dfrac{d - d_0}{d_1 - d_0} \times 100\right)\% の得点が与えられる.

備考

計算途中でのオーバーフローに注意すること.2^{32} = 4{,}294{,}967{,}296 である.C/C++ の場合は,必要に応じて,内部で double 型や long long int 型を用いて演算を行うと良いだろう.


Source Name

JOI 2006-2007 春季トレーニング合宿 Contest Day4