e033: 8. 摩天大樓
Tags :
Accepted rate : 0人/4人 ( 0% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-01-23 17:13

Content

強哥正在規劃某個摩天大樓的使用,這摩天大樓有n ≤ 25層樓,每一樓可以規劃成一戶或是建造一個公共設施,現在要同時安排住戶和公共設施的樓層分配,目的是要讓滿意度最低住戶的滿意度盡可能的高,而滿意度的定義如下:

 

公共設施有k ≤ 4個,而住戶有n-k戶。其中每一戶都會提供他們對這k個公共設施的厭惡程度,假設在某種排列下,公共設施被安排在樓層f1, f2, …, fk,而某住戶的樓層被安排在第ℓ樓且對這k個公共設施的厭惡程度是a1, a2, …, ak,則該住戶的滿意度定義為:

$\color{black}{\text{min}_{1 \le i \le k}|f_i - ℓ|a_i}$ 

強哥因為公務繁忙,並沒有時間好好規劃樓層的安排,請你寫一個程式將住戶和公共設施安排進這n層樓,使得滿意度最低住戶的滿意度盡可能地高。

Input

每一組測試資料有n-k+1行,其中第一行有兩個正整數n (2 ≤ n ≤ 25) 和k (1 ≤ k ≤ 4),且k < n,接下來的每一行代表n-k戶中的每一戶對k個公共設施的厭惡程度a1, a2, …, ak,每個ai都是介於1到100的整數 (1 ≤ i ≤ k)。

Output

對於每組測試資料,找出n! 所有可能的排列中,哪種排列可以讓滿意度最低住戶的滿意度盡可能地高,然後輸出在這個最佳排列下滿意度最低住戶的滿意度

Sample Input
輸入範例 1:
4 1
10
15
20

輸入範例 2:
4 2
1 3
1 2
Sample Output
輸出範例 1:
20

輸出範例 2:
2
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (2%): 2.0s , <1K
公開 測資點#1 (2%): 2.0s , <1K
公開 測資點#2 (2%): 2.0s , <1K
公開 測資點#3 (2%): 2.0s , <1K
公開 測資點#4 (2%): 2.0s , <1K
公開 測資點#5 (2%): 2.0s , <1K
公開 測資點#6 (2%): 2.0s , <1K
公開 測資點#7 (2%): 2.0s , <1K
公開 測資點#8 (2%): 2.0s , <1K
公開 測資點#9 (2%): 2.0s , <1K
公開 測資點#10 (2%): 2.0s , <1K
公開 測資點#11 (2%): 2.0s , <1K
公開 測資點#12 (2%): 2.0s , <1K
公開 測資點#13 (2%): 2.0s , <1K
公開 測資點#14 (2%): 2.0s , <1K
公開 測資點#15 (2%): 2.0s , <1K
公開 測資點#16 (2%): 2.0s , <1K
公開 測資點#17 (2%): 2.0s , <1K
公開 測資點#18 (2%): 2.0s , <1K
公開 測資點#19 (2%): 2.0s , <1K
公開 測資點#20 (3%): 2.0s , <1K
公開 測資點#21 (3%): 2.0s , <1K
公開 測資點#22 (3%): 2.0s , <1K
公開 測資點#23 (3%): 2.0s , <1K
公開 測資點#24 (3%): 2.0s , <1K
公開 測資點#25 (3%): 2.0s , <1K
公開 測資點#26 (3%): 2.0s , <1K
公開 測資點#27 (3%): 2.0s , <1K
公開 測資點#28 (3%): 2.0s , <1K
公開 測資點#29 (3%): 2.0s , <1K
公開 測資點#30 (3%): 2.0s , <1K
公開 測資點#31 (3%): 2.0s , <1K
公開 測資點#32 (3%): 2.0s , <1K
公開 測資點#33 (3%): 2.0s , <1K
公開 測資點#34 (3%): 2.0s , <1K
公開 測資點#35 (3%): 2.0s , <1K
公開 測資點#36 (3%): 2.0s , <1K
公開 測資點#37 (3%): 2.0s , <1K
公開 測資點#38 (3%): 2.0s , <1K
公開 測資點#39 (3%): 2.0s , <1K
Hint :

本題共有四個子題,每一子題可有多筆測試資料:

第一子題的測試資料中n ≤ 25、k = 1,全部解出可獲7分;

第二子題的測試資料中n ≤ 25、k ≤ 2,全部解出可獲8分;

第三子題的測試資料中n ≤ 25、k ≤ 3,全部解出可獲22分;

第四子題的測試資料中n ≤ 25、k ≤ 4,全部解出可獲63分。

Tags:
出處:
107學年度全國資訊學科能力競賽 [管理者:
icube (輸光光)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」