回分類題庫
d091: 2009 程式達人 E - 披薩配料問題
出處:

Difficulity : 1
Accepted : 15 Times | Submit :49 Times | Clicks : 1603
Accepted : 7 Users | Submit : 10 Users | Accepted rate : 70%
Time Limit :2001 ms | Memory Limit : 32001 KBytes
題目加入時間 : 2009-06-02 00:27

Content :

比賽到現在相信大家也累了,Aidnap也一直在喊餓。重案組組長衝哥決定犒賞一下大家,請大家吃大仁分局前面有名的披薩解解饞。

Okia披薩是知名連鎖蛋糕店─“Okia蛋糕”的關係企業。Okia披薩的口味眾多實在令人難以抉擇,然而在分局內有若干多的小組,每個小組都是一個不超過20人的TEAM,每個人的口味也不盡相同。每個人都有喜歡或不喜歡吃的東西,大家也心知肚明每個組就只能訂一個披薩(還記得我們預算有限),不可能滿足每個人的需求。衝哥有辦法提供每組「一個至少滿足每個人一項需求的披薩」嗎?


不,當然不可能!衝哥太衝了,他早就殺去披薩店了,所以只能請想吃披薩的你來寫程式幫忙了。Okia披薩提供了16種配料,分別是:

A.    舒服口味吃了會渾身舒服
B.    小愛口味吃了眼睛會變小
C.    紅蟲口味吃了學歷變博士
D.    L拍口味吃了變成科普王
E.    鈍鈍口味吃了頭腦也鈍鈍
F.    鋼彈口味吃了身體發紅光
G.    優優口味吃了頭腦會變革
H.    綠蠵口味吃了變成高鐵人
I.    小白口味吃了專心宅宿舍
J.    科西口味吃了熬夜趕專題
K.    藍路口味吃了領帶會亂跳
L.    科分口味吃了科科一百分
M.    生財口味吃了和氣又生財
N.    呆呆口味吃了會杯逼費私
O.    Gvv口味吃了腸胃炎失重
P.    Okia口味吃了視線變粉紅(本店招牌)

每個組員提供你他想要或不想要的配料,以下面的格式表示:

+O-H+P;

表示他想要配料O、不想要配料H、想要配料P。而

-E-I-D+A+J;

表示他不想要配料E、不想要配料I、不想要配料D、想要配料A、想要配料J。

Input :

輸入含有多組測試資料。每組測試資料包含了1到20位組員的需求,每個組員一列,以分號做結尾。若遇到僅含有一個 ”.” 的一列,代表此組測試資料結束。

Output :

對每組測試資料輸出一列。如果存在這種披薩配料組合,則先輸出 "Toppings:" 。緊接著以空白隔開,輸出披薩上的配方代碼(按字母順序輸出),使這個披薩能滿足每個人至少一項需求。

但是,如果答案不只一種組合,你也知道我們經費有限,所以如果有多種配料組合能夠滿足需求的披薩時,那就選套入下面這個價錢公式得到的金額最小的那種配料方式。

    假設輸出的字串長度k,分別由i0i1i2...ik來代表,期望值公式:

        ∑(j=0~k)(round(8^eff(ij )  ) )
    其中:
        eff(ij) = ( AsciiCode(ij)-AsciiCode(‘A’) ) / 3    
        AsciiCode(x)函數回傳x之Ascii Code。
        round(x)函數回傳x四捨五入之值。

如果沒有任何一種配方組合可以滿足每個人至少一項需求,請輸出:
”No pizza can satisfy these requests.”,請參考範例輸出。

Sample Input :

+A+B+C+D;
+E+F+H;
+A+B-G;
+O+J-F;
+H+I+C;
+P;
+O+M+L;
+M-L+P;
.
+A+B+C+D;
+E+F+F+H;
+A+B-G;
+P-O;
+O+J-F;
+H+I+C;
+P;
+O;
+O+M+L;
-O-P;
+M-L+P;
.
-A+O;
-I+K;
-D+I;
-N+A;
-A;
-P;
.

Sample Output :

Toppings: CELP
No pizza can satisfy these requests.
Toppings:

Hint :


  

Author :


  Solve it!   Status Forum (0)

C++
C
JAVA
49467. CC501 (32 ms , 272KB)
31827. henryokc (36 ms , 362KB)
38334. nothinglo (76 ms , 404KB)
38333. MK (82 ms , 414KB)
39689. MK (100 ms , 4506KB)
55496. ag100 (4 ms , 232KB)
7390. yuhanlyu (4 ms , 212KB)
55495. ag100 (6 ms , 242KB)
55497. ag100 (8 ms , 238KB)
55494. ag100 (8 ms , 236KB)
沒有解題記錄

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡