a671. 免費大餐 - Zero1 Online Judge System

Content

你正步入你的大學生涯的第一年，作為一個新生，有很多事情需要好好計劃一下。其中一項就是你每天晚上的晚餐。一個學期共有N餐晚餐。

你住在大學宿舍，大學規定一年級生必需留在大學餐廳用餐。然而，大學內有數間(M間)餐廳可選擇，而這些餐廳為了爭取客人，均提供一些優惠。出奇地，這些餐廳的優惠型式都是相同的，只是一些詳細內容不同而已。

優惠的規則如下：

餐廳在學期的第一天就會公佈該學期內每晚的晚餐內容及價錢
每個學生只能購買一間餐廳的餐卡，一旦購買了一間餐廳的餐卡，整個學期都需要在該餐廳用餐
每個學生每晚用餐時，他可以選擇交全費或享用節扣價(R%)，若學生選擇交全費的話，他就可以在他的餐卡上盖一個印章。但若享用節扣價的話，則不可以蓋印。
當一個學生的餐卡上印了K個或以上的印時，他可以選擇在進入餐廳時，用他的印有足夠印章的餐卡來換取免費享用當晚的晚餐，這時，餐廳就會收了他的那張餐卡，同時發給他一張全新(沒有任何印章)的餐卡。之後這位學生可以繼續用他的全新餐卡重新開始儲印章來換取其後免費晚餐。

每間餐廳都使用同樣的方法來提供優惠，所不同的是晚餐的內容，每餐的價錢，及相關的節扣率R及要求的印章數目K。

當然，晚餐的內容是個很重要的因素，但費用的多少也是一個不得不考慮的因素。於是你想找出利用餐廳提供的優惠方案，要在整學期在某一間餐廳所需要付的最少費用會是多少？因為你在某一間餐廳選擇何時付全費，享用節扣價或享用免費大餐會有不同的結果。

Input

輸入的第一行有兩個正整數：N, M，它們分別代表晚餐數目，餐廳的數目( 1 <= N <= 100, 2 <= M <= 500 )

隨後有M行，每行給出一間餐廳的情況，每行均有 N + 2 個數字：S R P₁ P₂ P₃ ... P_N

S為一正整數，它代表最少要有多少個印章才可換一次免費晚餐
R是個正整數，它代表可享用的節扣率為R%
隨後的N個數均為正整數，它們順次表示每晚用餐的費用，餐費最高為 1,000

Output

輸出應該有 M 行，每行有一個小數 ( 少數點後有兩個位 )，它代表在一間餐廳用餐所需要的最低價錢。

Sample Input #1

8 2
4 75 30 30 30 60 30 35 90 50
3 80 40 40 35 65 30 32 120 110

Sample Output #1

228.75
297.00

測資資訊：

記憶體限制： 64 MB
不公開測資點#0 (10%): 1.0s , <1K
不公開測資點#1 (10%): 1.0s , <1K
不公開測資點#2 (10%): 1.0s , <1K
不公開測資點#3 (10%): 1.0s , <1K
不公開測資點#4 (10%): 1.0s , <1M
不公開測資點#5 (10%): 1.0s , <1M
不公開測資點#6 (10%): 1.0s , <1M
不公開測資點#7 (10%): 1.0s , <1M
不公開測資點#8 (10%): 1.0s , <1M
不公開測資點#9 (10%): 1.0s , <1M

Hint ：

對第一個餐廳計劃是：30 + 30 + 30 + 60*0.75 + 30 + 35*0.75 + 90*0 + 50*0.75 = 228.75

對第二個餐廳計劃是：40 + 40 + 35 + 65*0 + 30 + 32 + 120 + 110*0 = 297.00

#非官方測試數據

Tags:

出處:

MOI 2021 [管理者：

lamkinun@gma... (Kinda Lam)

]

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