e760. 658 - It's not a Bug, it's a Feature!
Tags :
Accepted rate: 20人/ 21人 ( 95%) [非即時]
評分方式:
Tolerant

最近更新 : 2019-12-26 21:31

Content

現在你的電腦有所有$n$個bug,你需要安裝$m$種補丁,但是補丁也是會產生bug的。

每個補丁的安裝都需要耗費$m_i$單位時間,補丁的安裝次數不限。

問最少需要多少單位時間把所有bug修好。

Input

輸入包含多筆測資。

每筆測資都有兩整數$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$時,測資結束。

Output

對於每筆測資請先輸出是第幾筆(i.g. "Product 2"),換一行,再依格式輸出答案(i.g. "Fastest sequence takes 8 seconds.")。

每個答案之間請空一行。

如果無法修復所有bug請輸出"Bugs cannot be fixed."

Sample Input #1
3 3
1 000 00-
1 00- 0-+
2 0-- -++

4 1
7 0-0+ ----

0 0
Sample Output #1
Product 1
Fastest sequence takes 8 seconds.

Product 2
Bugs cannot be fixed.
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <1M
Hint :
Tags:
出處:
UVa 658 - It's not a Bug it's a Feature! [管理者: qqrainbow (愛蜜莉雅) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」