以下是来自日本的官方新闻原版PDF,已经完整保存和染色。



可复制的 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