現在你的電腦有所有$n$個bug,你需要安裝$m$種補丁,但是補丁也是會產生bug的。
每個補丁的安裝都需要耗費$m_i$單位時間,補丁的安裝次數不限。
問最少需要多少單位時間把所有bug修好。
輸入包含多筆測資。
每筆測資都有兩整數$n$, $m$,代表有$n$個bug,$m$種補丁。
$1\leq n \leq 20$ $1\leq m \leq 100$
接下來會有$m$行,每行包含一個整數,代表安裝所需的時間,以及兩個字串。
兩個字串只包含'+', '-', '0',
$S1_i = '+'$代表如果想安裝此補丁,需要第i個bug存在。
$S1_i = '-'$代表如果想安裝此補丁,需要第i個bug不存在。
$S1_i = '0'$代表如果想安裝此補丁,不需要依賴第i個bug存在與否。
$S2_i = '+'$代表如果安裝此補丁,將會引起第i個bug。
$S2_i = '-'$代表如果安裝此補丁,將會修復第i個bug。
$S2_i = '0'$代表如果安裝此補丁,將不會引起第i個bug,也不會修復第i個bug。
每筆測資中間會空一行。
當$n = m = 0$時,測資結束。
對於每筆測資請先輸出是第幾筆(i.g. "Product 2"),換一行,再依格式輸出答案(i.g. "Fastest sequence takes 8 seconds.")。
每個答案之間請空一行。
如果無法修復所有bug請輸出"Bugs cannot be fixed."
3 3 1 000 00- 1 00- 0-+ 2 0-- -++ 4 1 7 0-0+ ---- 0 0
Product 1 Fastest sequence takes 8 seconds. Product 2 Bugs cannot be fixed.
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|