c942: 露營區規劃
Tags :
Accepted rate : 10人/10人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2018-12-08 08:40

Content
綠野露營區環境清幽,為眾人所喜愛。營區的規劃為 N 個環狀的區域(N<10),各個圓環的半徑不一定相同(R1、R2、...、Rn),
營帳位置點就設定在環狀的邊緣上,且各點之間有環狀小路相連。今老闆因為成本考量,希望能規劃 K 個露營點,但又希望
能給予每個露營點的朋友享受最大的私人空間。請寫一個程式幫老闆解決這個頭痛的問題吧!
範例1: 有兩個圓(R1=10、R2=6),希望規劃露營點數 M=5
輸出結果,在圓1 中可放置 3 個點,圓2 中可放置 2 個點 (各點之間最短環狀距離約為 18.85,如下圖所示)

Input
多筆測資,每筆測資共兩行,0 0 結束。
測資第一行為整數N、M,代表共有 N 個圓形區域,共規劃 M 個露營點。
第二行有 N 個整數,代表各圓的半徑 R1、R2、...、Rn 
(1<=N<=10   測資保證每個圓都至少有一個露營點
Output
每筆測資一行,輸出 N1  N2  ...  Nn,數字間隔一個空白,
N1~Nn 為各圓可規劃的露營點數。
Sample Input
2 5
10 6
0 0
Sample Output
3 2
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (33%): 1.0s , <1K
不公開 測資點#1 (33%): 1.0s , <1K
不公開 測資點#2 (34%): 1.0s , <1K
Hint :

二分搜尋

Tags:
出處:
林口高中校內選訓 [編輯:
hshua (hshua)
]


ID User Problem Subject Hit Post Date
16859
054025 (東翰)
c942
除了二分的方法
15 2019-02-14 20:34