← 返回题目列表

AtCoder · joisc2007_packing5

packing5. 半导体工厂(包装)

中文机器翻译题面 查看原题

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

半導体工場 (Packing) - 原题 PDF 第 1 页
原题PDF第5页
半導体工場 (Packing) - 原题 PDF 第 2 页
原题PDF第6页
半導体工場 (Packing) - 原题 PDF 第 3 页
原题PDF第7页
可复制的 PDF 提取文本
Packing: 半導体工場

出力のみの課題(OUTPUT ONLY TASK)・相対評価


input 問題文中で与えられる.
output ファイル“packing-outk.txt” (k = 1, 2, 3, 4, 5)



 あなたの勤めている半導体工場では,最新鋭の装置を用いてシリコン板を加工し,半導体チッ

プの材料として出荷している.シリコン板の加工に用いる装置は極めて高精度であり,加工位

置を10 ナノメートル単位で調整することができる(10 ナノメートル= 100,000,000 分の1 メー

トル).

 ある顧客からの注文により,あなたは,辺の長さが1 メートルの正方形のシリコン板から,n

枚のシリコン円板を切り抜くことになった.切り抜くシリコン円板は全て同じ大きさでなけれ

ばならない.また,貴重なシリコン板を無駄にしないよう,できるだけ大きい円板を切り抜く

ことが望ましい.

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

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

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


Output. 出力データをファイルとして提出せよ.出力データの作成方法は問わない.プログ

ラムに直接生成させてもよいし,必要に応じて,それをテキストエディタ等で加工してもよい.

出力データの作成に用いたプログラムを提出する必要は無い.

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

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

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

書く必要はない.

                      半導体工場–1/3

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

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

      25000000 25000000

      75000000 25000000

      25000000 75000000


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





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

      74540929 25404070

      25474639 38662789

      61538179 74593059


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





                       半導体工場–2/3

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

結果を与える.

     50993849 72645350

     17399669 81993059

     83110119 83073720

     50245039 25147290

     83063380 16879409

     16948019 16965430

     26471179 49375439

     76212739 50011850


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





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

   • 出力データが誤っていた場合や未提出の場合は,その出力データに関する得点は0 点であ

   る.また,半径が「モデル解法」以下の出力データも0 点である.

   • 「モデル解法」よりも半径の大きなデータが提出された場合,その得点は次のようにして
   計算される.「モデル解法」の半径をd0 とおく.提出された出力データの半径のうち,最も
   大きいものをd1 (d1 > d0) とおく.半径d  (d1 ≧d ≧d0) の出力データには,配点のうち,
                       µ        ¶
                                    d −d0
                           × 100  %
                                          d1 −d0

   の得点が与えられる.


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

                      半導体工場–3/3