2013年7月23日 星期二

11566 - Let's Yum Cha!



Yum cha 是粵語中的用來描述 "飲茶" 的術語,指吃不同的小點心,同時喝著中國茶的一種文化。飲茶是中國廣東與香港文化中的一部分,對廣東人來說,飲茶傳統上會在週末早上,全家人聚在一起聊天吃點心、喝喝中國茶,而茶是最重要的, 用來幫助消化食物。在過去,人們常去茶館飲茶,但是近幾年中,點心餐廳普及已經勝過茶館。



點 心在中文字面意思上 "點觸你的心",點心可選擇的範圍相當廣泛,包括肉類、海鮮、甜品及水果的各種組合,點心通常藉由蒸的或者是油炸的烹飪方式,通常是用蒸籠或者是小盤子裝 著呈上來,而通常是三四件點心一盤,由於分量小,因此可以嘗試非常多樣的點心,最常見的點心有:'





·  Har gow: A delicate steamed dumpling with shrimp filling and thin (almost translucent) wheat starch skin. It is one of my favourite dim sum.
·  Siu mai: A small steamed dumpling with pork inside a thin wheat flour wrapper. It is usually topped off with crab roe and mushroom.
·  Char siu bau: A bun with Cantonese barbeque-flavoured pork and onions inside. It is probably the most famous dim sum around the world.
·  Sweet cream bun: A steamed bun with milk custard filling. It is sweet and spongy.
·  Spring roll: Consists of sliced carrot, wood-ear fungus, and sometimes meat, rolled inside a thin flour skin and deep-fried. It is crispy and delicious.
右圖即上述描述的點心,你能夠猜出是哪幾道嗎?

今天有 N 位朋友一起飲茶,你和你的朋友將會付一樣的錢,而每個人(包括你) 最多付 $x,而餐廳有 K  種點心可以點,而對於一種點心,每個人將會獲得一個喜愛指數(favour index),範圍介於 0 ~ 10 的整數。

現在將要點餐,你想要最大化自己的喜愛指數的總和,但是如果忽略朋友的喜愛點心,你將會被狠狠地痛打一頓,因此你改成要最大化平均每個人得到的喜愛指數,根據以下的公式

$$\frac{\text{Total favour value of all dishes ordered}}{N+1}$$

將這個公式計算出來的稱為 "mean favour value",這並不表示每個人都會拿點心來吃,但是朋友總是會一起分享點心,來讓每個人都開心。

由於想要點多一點不同種的點心 ,你將不會點同一種點心大於 2 次,而且為了不浪費食物,也不會點大於 2(N+1) 盤點心,也就是每個人點 2 盤。帳單在計算時,不會只有點心的價錢,還會加上兩種基本費。 茶費: 每個人需要支付 $T 元的茶費。 10% 服務費: 在所有花費加總後,會再加收 10% 的服務費,採用無條件進位。


輸入最多 25 組測資, 每組測資第一行會有四個整數 N, x, T, K,分別代表的如上描述

1 N ≤ 10, 1 ≤ x ≤ 100, 0 ≤ T ≤ 20, 1 ≤ K ≤ 100, $1 ≤ price of a dim sum ≤ $100. 

接著會有 K 行,每行表示點心的訊息,第一個整數表示點心的價錢,接著會有 N+1 個整數表示喜愛指數。

 N = x = T = K = 0,結束程式


對於每組測資,輸出一行最大的 "mean favour value",精準到小數點第二位。


3 10 5 2
6 7 5 6 9
10 9 10 10 8
0 0 0 0


16.00