/
実行時間制限: 1 sec / メモリ制限: 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
これを図示すると下図の通りである.
例 2
例 1 は最適解ではない.例えば,
74540929 25404070 25474639 38662789 61538179 74593059
の方が良い結果を与える.これを図示すると以下の通りである.
例 3
以下は,n = 8 の場合の出力データの例である.このデータは,「モデル解法」よりも良い結果を与える.
50993849 72645350 17399669 81993059 83110119 83073720 50245039 25147290 83063380 16879409 16948019 16965430 26471179 49375439 76212739 50011850
これを図示すると以下の通りである.
採点について
出力データ毎に配点を定め,以下に従い,相対評価で採点を行う.
- 出力データが誤っていた場合や未提出の場合は,その出力データに関する得点は 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 型を用いて演算を行うと良いだろう.