回分類題庫
z091: C 紀念品排隊問題
關鍵字: NPSC2013國中決賽

測資點 : 1 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 15 Times / 14 Users | Submit : 21 Times / 15 Users | Accepted rate : 93%
題目加入時間 : 2019-11-18 17:24

Content: 简体中文

皮皮是一個名為「超 ⋆ 可魚」的偶像團體的忠實粉絲 (fans),目前這個團體舉辦過的每一場演 唱會他都有參加。
而最近這幾年的演唱會,除了本身的演出之外,販賣的週邊商品往往造成了所謂的「第二個戰 場」。在「限量」二個字的面前,幾乎所有死忠粉絲都會為之瘋狂。然而,所謂的週邊商品,已經 幾乎變成有錢也不一定能夠買得到的東西了。尤其是比較有名的歌手或團體 (例如「超 ⋆ 可魚」 就是其中之一) 的演唱會週邊商品,更是時常「一份難求」。 這次,皮皮正打算參加 2013 年底所舉辦的「超 ⋆ 可魚之 2013 年終巡迴演唱會」,而他當然也 不會錯過這次演唱會的週邊商品販賣。為了買到儘量多的週邊商品,皮皮 (以及其他忠實粉絲們) 往往需要一大清早就到場排隊才能夠買到想要的商品。
在冗長的等待過程中,皮皮突然發現到一個有趣的現象:「由於這次已經是巡迴演唱會的最後 一站,有些在前面排隊的粉絲已經擁有一些準備要販賣的商品了!」例如皮皮就發現前面有一位粉 絲已經穿著這次巡迴演唱版本的限量 T-shirt,而有另一位粉絲已經戴著專屬護腕。根據皮皮的認 知,「超 ⋆ 可魚」的粉絲們都非常 nice,會傾向於把自己已經有的東西留給別人,故我們可以假 設「如果一位粉絲已經有了某樣物品,則那位粉絲就不會再購買該物品」。
在排隊之餘,皮皮想要根據排在前面的人的「已購買」資訊,來推測出「運氣最差時至少可以 買到多少種商品」。簡單來說,皮皮想要知道,「就算前面每個人都買了所有他/她還沒有擁有的商 品,皮皮仍確定可以買到多少種商品」。
在這題中,我們假設每位粉絲每項商品最多只會購買一份;除此之外,皮皮會觀察到排在他前 面的所有粉絲們所擁有的物品。

Input:

輸入的第一行有一個正整數 T (T ≤ 50),代表測試資料的組數。 每一組測試資料的第一行有兩個整數 S (1 ≤ S ≤ 100) 和 N (1 ≤ N ≤ 100),中間以一個空白 隔開。S 代表這次所販賣的商品總數,N 為排在皮皮前面的人數。
之後有 S 行,每一行即代表一項這次要販賣的演唱會週邊商品,包含商品名稱及該商品的總販 賣數量,中間以一個空白隔開。
接著有 N 行,第 i 行包含第 i 位排在皮皮前面的粉絲的擁有物品清單。每一行首先有一個正 整數 ki,代表第 i 位粉絲已經擁有的商品數量。之後有 ki 個字串,代表第 i 位粉絲擁有的商品名 稱。商品數量與名稱各以一個空白隔開。 所有出現的商品名稱長度都不會超過 128,並且,所有的商品名稱都是以英文字母組成的 (大 小寫視為不同)。另外,每種商品的販賣數量保證不會超過 1000。 

Output:

對於每一筆測試資料,請輸出一行。
• 如果皮皮很可憐,什麼都買不到的時候,請輸出 “Need to be lucky” (不包含雙引號)。
• 反之,請輸出一個正整數,表示皮皮至少可以買到幾種商品。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
3 
5 4 
Tshirt 10 
Watch 4 
Towel 3 
HandLight 10 
LimitedBook 1 
1 Tshirt 
1 Tshirt 
2 Tshirt Watch 
2 Tshirt HandLight 
2 2 
LimitedCD 1 
Handring 1 
1 Handring 
1 LimitedCD 
2 2 
ABCDEFGHIJKLMNOPQRSTUVWXYZ 1 
abcdefghijklmnopqrstuvwxyz 1 
1 ABCDEFGHIJKLMNOPQRSTUVWXYZ 
1 ABCDEFGHIJKLMNOPQRSTUVWXYZ

Sample Output :


  

Hint :


3
Need to be lucky
1

Author :

NPSC2013國中決賽 (管理員:Chang)

  Solve it!   Status Forum