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



可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2011/2012
Spring Training Camp/Qualifying Trial
March 19–25, 2012, Komaba/Yoyogi, Tokyo
Contest Day 2 – Broadcasting
テレビ放送(Broadcasting)
出力のみの課題(Output-only task)
JOI 国ではこの度,テレビ放送を開始することになった.JOI 国にはN 戸の家がある.これらすべての家
でテレビ放送が見られるようにするため,電波塔を建てる必要がある.
今回JOI 国の国王はK 本の電波塔を建てることに決めた.i 番目の電波塔を座標(Xi, Yi) に建て,出力レ !
ベルをEi に設定すると,(Xi, Yi) からの距離が Ei 以下の家でテレビ放送が見られるようになる(2 点(a, b) !
と(c, d) の距離は (a −c)2 + (b −d)2 で与えられる).ただし,電波塔の出力レベルをEi に設定するとEi
のエネルギーを消費する.すべての家でテレビ放送が見られるようにしつつ,できるだけK 本の電波塔で
消費されるエネルギーの合計(以下,単に「消費エネルギー」と呼ぶ) を少なくしたい.電波塔は家がある
座標に建てることもできるし,同じ座標に2 つ建てることもできる.
JOI 国の家の座標が与えられた時,すべての家でテレビ放送が見られるように電波塔を建てる場所と出
力レベルの設定を決めたい.
課題
JOI 国の家の位置およびK が与えられるので,電波塔を建てる場所と出力レベルの設定を出力せよ.消
費エネルギーが少ないほど,あなたは高得点を得る.
制限
1 ≦N ≦500 JOI 国の家の数
1 ≦K ≦30 今回建てる電波塔の数
0 ≦Ai, Bi ≦1 000 000 家の座標
入力
入力ファイルは以下の形式で与えられる.
• 1 行目には整数N, K が空白を区切りとして書かれており,JOI 国の家の数がN, 今回建てる電波塔の
数がK であることを表す.
• 続くN 行のうちi 行目(1 ≦i ≦N) には整数Ai, Bi が空白を区切りとして書かれており,i 番目の家の
座標が(Ai, Bi) であることを表す.
同じ座標に2 つ以上の家があることはないとしてよい.
テレビ放送– 1 / 3
Japanese Olympiad in Informatics 2011/2012
Spring Training Camp/Qualifying Trial
March 19–25, 2012, Komaba/Yoyogi, Tokyo
Contest Day 2 – Broadcasting
出力
出力のi 行目(1 ≦i ≦K) には3 つの整数Xi, Yi, Ei (0 ≦Xi ≦1 000 000, 0 ≦Yi ≦1 000 000, 0 ≦Ei ≦
1 000 000 000 000 (= 1012)) を空白を区切りとして出力せよ.
提出方法
各入力データに対する出力を提出せよ.その際,出力のセクションで指定された形式に一致するかがチェッ
クされる.
採点基準
各入力データに対し,あなたの得点は以下のように計算される.
参加者が提出した出力の中での,消費エネルギーの最小値をE0 とする.あなたの提出した出力が問題の
条件を満たさない場合,あなたの得点は0 である.条件を満たす場合,あなたの提出した出力における消
費エネルギーをE として,
E
• E0 > 1.5 のとき,0
%
E ≦1.5 のとき, 4 1.5 20 の小数第1 • E0 × −EE0 &2× 位を四捨五入した値
があなたの得点となる.
テレビ放送– 2 / 3
Japanese Olympiad in Informatics 2011/2012
Spring Training Camp/Qualifying Trial
March 19–25, 2012, Komaba/Yoyogi, Tokyo
Contest Day 2 – Broadcasting
入出力例
入力例 出力例
10 3 200000 700000 160000000000
0 300000 300000 300000 90000000000
500000 800000 750000 0 62500000000
700000 200000
100000 500000
400000 900000
200000 1000000
300000 500000
300000 200000
500000 100000
1000000 0
!
この入出力は下の図に対応している.各々の円が座標(Xi, Yi) から距離 Ei 以下の範囲を表す.この場
合,消費エネルギーは160 000 000 000 + 90 000 000 000 + 62 500 000 000 = 312 500 000 000 (3125 億) である.
テレビ放送– 3 / 3