c942: 露營區規劃
標籤 :
通過比率 : 100% (4 人 / 4 人 ) (非即時)
評分方式:
Tolerant

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

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

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

二分搜尋

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


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」