回分類題庫
h108: A.曉涵的紙牌遊戲
關鍵字: NPSC 2012 高中組決賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 19 Times / 18 Users | Submit : 33 Times / 18 Users | Accepted rate : 100%
題目加入時間 : 2013-11-07 13:26

Content: 简体中文

曉涵和朋友們最近流行玩一個遊戲:首先準備好一疊紙牌,每張紙牌都有一個編號,編號為 1 到 N 之間的正整數,假設現在共有 P 位玩家(包含曉涵在內),則每個編號都分別有 P 張紙牌(故共有 P×N 張紙牌)。之後,每個人分別寫下一些「禁忌序列(forbidden sequence)」,每個禁忌序列都是一串遞增的編號,長度和序列內的編號由每個玩家自行決定,但編號不可重複,並且在遊戲開始前都不能給其他人看到。

大家都寫完自己設計的禁忌序列之後,由一個人將這 P×N 張紙牌拋起、使其散落在地板上,同時,大家都公布出自己設計的禁忌序列,此時遊戲正式開始!遊戲的目標在於,玩家要從散落的紙牌中找出一個比其他玩家都長的遞增序列以獲得勝利,其中不能存在超過一張同樣編號的紙牌,且遞增序列長度必須至少為 2 (至少要選兩張紙牌) ,且其中不可以包含任何人(包括自己) 所設計的禁忌序列。假設有一個人的禁忌序列是「1, 2, 4」,則「1, 2, 4, 5」便是不合法的遞增序列,但「1, 2, 3, 4」則是合法的。當然,像「1, 1, 2, 2」由於有同樣編號的紙牌,所以也是不合法的。

對於這個紙牌遊戲,好奇的曉涵除了想要贏之外,她還想要知道在給定大家的禁忌序列的情況下,究竟有多少種不同的合法遞增序列呢?然而慢慢數真的太累了,請你寫一個程式來幫曉涵計算出總共有多少種不同的遞增序列。 

Input:

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

每筆測試資料第一行有一個整數 N (2<=N<=10),表示紙牌的最大編號。第二行有一個整數 P (2<=P<=10) 代表共有多少位玩家(包含曉涵在內)。

之後從第三行開始共有 P 行,每一行包含一位玩家所設計的「禁忌序列」。首先有一個正整數 Li (2<=Li<=N),代表該玩家所設計的禁忌序列的長度,之後有 Li 個正整數,依序代表該禁忌序列中的各個編號。所有人設計的禁忌序列都是遞增的且其中包含的編號都是在 1 到 N 之間。

由於玩家之間遊戲前是看不到其他人設計的禁忌序列的,所以可能會有多位玩家設計出相同的禁忌序列。 

Output:

對於每一組測試資料請輸出一行,該行包含一個正整數代表共有多少種不同的遞增序列。

如果沒有任何遞增序列是合法的話,請輸出一行 "so sad" (不含引號)。 

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
4
5
3
3 2 3 4
2 2 3
2 2 4
7
2
2 1 2
2 6 7
5
4
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5
3
4
2 1 2
2 2 3
2 1 3
3 1 2 3

Sample Output :

14
64
25
so sad

Hint :

Author :

NPSC 2012 高中組決賽 (管理員:sagit)

  Solve it!   Status Forum