回分類題庫
h119: D.RPG 遊戲之料理奇蹟
關鍵字: NPSC 2013 高中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 28 Times / 24 Users | Submit : 76 Times / 27 Users | Accepted rate : 89%
題目加入時間 : 2013-12-17 13:37

Content: 简体中文

身為一位專業的 RPG (角色扮演) 類型電玩遊戲愛好者,卡恩總是想要把所有可能的支線劇情、隱藏事件、對話,以及每個小細節都玩過。也因為這樣,卡恩有的時候會發現一些遊戲設計上的問題,如某種情形之下角色會被傳送到奇怪的地方、莫名的卡點當機等等。 

這一次,熱愛 RPG 遊戲的卡恩正在玩日本某F 公司的著名系列作「軌跡人生」。在這次最新發行的作品中,主角可以藉由翻閱書籍或者是與 NPC (非玩家角色) 對話學會製作各種料理,並可以將習得的料理記錄在料理手冊中,而之後只要有符合需求條件的食材,便可以依照料理手冊中所記載的食譜,製作出相對應的料理品項。

除此之外,在遊戲中,大部分的食材都來自於戰鬥中怪物所掉落的物品,但也有些食材是在 NPC 所開設的商店中就可以買到的,每項製作出來的料理也都可以於 NPC 所開設的商店中售出。對於這樣子的系統,卡恩馬上就想到· · · · · · 「有沒有可能可以從中賺錢呢?」

請你寫個程式幫卡恩確認看看,以現在卡恩所持有的料理手冊內容而言,是否能夠藉由料理系統賺錢。精確地說就是,請你找出「所需要的食材都可以從商店中買到並且賣出的價錢會大於所需原料的總價錢」的料理。 

Input:

輸入的第一行有一個正整數 T (T<=50),代表測試資料的組數。

每一組測試資料的第一行有兩個整數 S (1<=S<=1024) 和 N (1<=N<=1024),兩個整數中間以一個空白隔開。S 為 NPC 商店所販賣的食材種類數,N 為卡恩的料理手冊中所記載的食譜數量。

之後有 S 行,每一行即代表一項 NPC 商店中所販賣的食材,包含食材名稱及該食材一份的價錢,中間以一個空白隔開。

接著有 N 行,每一行即代表一項卡恩的料理手冊中的料理及其食譜,包含料理名稱、該料理賣出一份的價錢,以一個空白隔開;之後有一個冒號「:」(不含引號,冒號前後皆有一個空白),後面接著的內容為所需要的食材列表,表示的方法為「數量1」、「食材名稱1」、「數量2」、「食材名稱2」 · · · · · · ,中間都以一個空白隔開。所需要的單一食材數量皆不會超過 99。在一份食譜中,保證不會出現重複的食材名稱。 

需要注意的是,就如同前言所說的,食譜中所需要的食材並不一定能夠在 NPC 商店中買到。對於包含買不到的食材的這些料理,我們將「不考慮它們為可賺錢的料理」。

方便起見,所有的食材名稱都被編碼為一個正整數的編號,並以 item 作為開頭;所有的料理名稱也都被編碼為一個正整數的編號,並以 food 作為開頭。所有的價錢則是以 $ 符號為開頭的正整數。所有的編號都不會大於 99999 ,所有的價錢都不會超過 99999999 ,請參考下方的範例輸入。 

Output:

對於每一筆測試資料,請輸出一行,包含所有可以賺錢(根據題目定義) 的料理名稱。如果有超過一種料理符合條件,請「按照編號的數值大小順序全部輸出」,並以斜線「/」(不含引號) 隔開。

如果卡恩的料理手冊中沒有存在任何能夠賺錢(根據題目定義)的料理的話,請輸出一行「no such recipe.」(不含引號)。

請參考下方的範例輸出。 

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3
3 5
item1001 $20
item1002 $10
item1003 $25
food9001 $50 : 1 item1001 2 item1002
food9002 $100 : 4 item1003
food7001 $101 : 2 item1001 1 item1002 2 item1003
food10002 $77 : 1 item1001
food10004 $50 : 1 item1001 2 item1002
1 2
item1 $1
food1 $99999999 : 1 item1 1 item2
food2 $99999999 : 99 item1
3 1
item99999 $99999997
item99998 $99999998
item99997 $99999999
food514 $99999999 : 99 item99999

Sample Output :

food7001/food9001/food10002/food10004
food2
no such recipe.

Hint :

Author :

NPSC 2013 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum