---
# System prepended metadata

title: 多處理機平行程式設計 作業1-1說明

---

# 多處理機平行程式設計 作業1-1說明


## 題目:程式設計師不要偷懶！

### 題目敘述

驗證一個程式是否正確的其中一種方法是執行測試，為了確保程式在各種奇怪的情況下都能正確執行，有一種測試方法為隨機測試$（$random/fuzzy test$）$。假設我們有超多種測試，各自涵蓋程式的某個部份，我們希望選出一些測試可以涵蓋整個程式得以完整測試。我們假設整個程式 $P$ 被分成 $n$ 個部份，即 $P$ $=$ $\lbrace A_1, A_2, ... , A_n \rbrace$ ，而所有的測試 $T$ 內共有 $m$ 種，即 $T$ $=$ $\lbrace S_1, S_2, ... , S_m \rbrace$，每個 $S$ 各自涵蓋一些 $A$。很不幸的是每種測試都有各自的執行成本，所以最理想的狀況是選出一些測試不僅要涵蓋整個程式，還要是最低成本，避免測試跑太久被當作程式設計師偷懶的藉口（就像編譯太久也會被當作玩耍的藉口一樣）。在此我們想要先知道總共有幾種組合是可以涵蓋整個程式。


### 輸入輸出說明

第一行含有兩個數字 $n$ 和 $m$，分別為程式 $P$ 共由幾個部份組成，及共有 $m$ 種測試，其中$1$ $\leq$ $n$, $m$ $\leq$ $32$。接下來的 $2m$ 行每兩行為一種測試的兩種資訊，分別為：
$\quad$• 第一行：此測試涵蓋的部份的數量，以及測試成本
$\quad$• 第二行：此測試涵蓋了程式的哪些部份

例如：
$\quad$$2$ $3$
$\quad$$1$ $2$
$\quad$$1$
$\quad$$1$ $2$
$\quad$$2$
$\quad$$2$ $3$
$\quad$$1$ $2$
第一行含有 $n$ 為 $2$ 以及 $m$ 為 $3$，第二行表示這筆測試共涵蓋 $1$ 個部份，成本為 $2$，第三行表示這筆測試涵蓋第 $1$ 部份的程式，接下來每兩行以此類推。
這個範例總共有 $5$ 種組合是可以涵蓋整個程式。請以以下格式輸出
$\quad 5$

### 繳交格式

在Github上傳一個程式碼檔案<font color="#f00">以及對應的Makefile檔案</font>，程式碼檔名為 學號_hw1_1 
例如：p12345678_hw1_1.c p12345678_hw1_1.cpp都可
Makefile就叫Makefile