2007-day4-packing-prob - 情報オリンピック攻略Wiki

半導体工場 (Packing)

出力のみの課題 (Output-only task)

---

　あなたの勤めている半導体工場では，最新鋭の装置を用いてシリコン板を加工し，半導体チップの材料として出荷している．シリコン板の加工に用いる装置は極めて高精度であり，加工位置を10 ナノメートル単位で調整することができる(10 ナノメートル= 100,000,000 分の1 メートル)．
ある顧客からの注文により，あなたは，辺の長さが1 メートルの正方形のシリコン板から，n枚のシリコン円板を切り抜くことになった．切り抜くシリコン円板は全て同じ大きさでなければならない．また，貴重なシリコン板を無駄にしないよう，できるだけ大きい円板を切り抜くことが望ましい．
　正方形のシリコン板から，できるだけ大きなn 枚のシリコン円板を切り抜く方法を求めよ．

入力

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

出力

　出力データをファイルとして提出せよ．出力データの作成方法は問わない．プログラムに直接生成させてもよいし，必要に応じて，それをテキストエディタ等で加工してもよい．出力データの作成に用いたプログラムを提出する必要は無い．
データ番号k の入力に対する出力ファイル名はpacking-outk.txt である(k = 1, 2, 3, 4, 5)．出力データはn 行からなる．n は切り抜くシリコン円板の枚数であり，入力 の項で与えられている．i 行目(1 ≦ i ≦ n) には，i 枚目のシリコン円板の中心の位置を表す2 つの整数x_i, y_iを空白を区切りとして出力せよ．これは，i 枚目のシリコン円板の中心が，正方形板の左端からx_i × 10ナノメートル，上端からy_i × 10 ナノメートルの場所であることを意味する．x_i, y_i は0 ≦ x_i, y_i ≦ 100, 000, 000 をみたす整数である．
　切り抜くシリコン円板の大きさは，装置により自動的に計算されるので，出力データの中に書く必要はない．

モデル解法　この問題の一つの解法は次のようなものである．(m-1)² < n ≦ m² をみたす整数mを求める．正方形板をm × mの小正方形板に分割する．そこからn 個の小正方形板を選び，内接する円板を切り抜く．これにより，半径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₀ とおく．提出された出力データの半径のうち，最も大きいものをd₁ (d₁ > d₀) とおく．半径d (d₁ ≧ d ≧ d₀) の出力データには，配点のうち，

の得点が与えられる.

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

コメント