1890 問(wèn)題 G: 藍(lán)橋杯算法提高VIP-Petri Net Simulation
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 7 解決: 3
題目描述
一個(gè)Petri網(wǎng)是一個(gè)計(jì)算模型，用來(lái)說(shuō)明并發(fā)事件。每個(gè)Petri網(wǎng)包含一些庫(kù)所（被表示成圓圈），變遷（被表示成黑色的矩形），和一些有向邊，用來(lái)連接庫(kù)所到變遷，和變遷到庫(kù)所。每個(gè)庫(kù)所能夠包含0個(gè)或多個(gè)令牌（被表示成黑點(diǎn)）。
這里有2個(gè)例子：
在上面的第一個(gè)Petri網(wǎng)中，有2個(gè)庫(kù)所（P1 和 P2）和2個(gè)變遷（T1 和 T2）。P1初始有1個(gè)令牌。P2沒(méi)有令牌。P1是變遷T1的輸入庫(kù)所，P2是T1的輸出庫(kù)所。在第二個(gè)例子中，有3個(gè)庫(kù)所和3個(gè)變遷，P1有3個(gè)令牌。T2有2個(gè)輸入庫(kù)所，2個(gè)都是P2。
一個(gè)Petri網(wǎng)的操作
每個(gè)Petri網(wǎng)的變遷要么被允許，要么不被允許。一個(gè)變遷被允許當(dāng)且僅當(dāng)每個(gè)輸入庫(kù)所都至少有1個(gè)令牌。任何被允許的變遷可以發(fā)生。如果有多個(gè)變遷被允許，任何一個(gè)都可能發(fā)生。當(dāng)一個(gè)變遷發(fā)生時(shí)，每個(gè)輸入庫(kù)所都會(huì)移除1個(gè)令牌，每個(gè)輸出庫(kù)所都會(huì)增加1個(gè)令牌。這會(huì)有效地利用原子能來(lái)完成，作為一個(gè)事件。如果沒(méi)有一個(gè)變遷被允許，這個(gè)Petri網(wǎng)就被認(rèn)為是死的。
最上面那個(gè)例子，只有T1是被允許的。當(dāng)它發(fā)生時(shí)，會(huì)從P1移除1個(gè)令牌，給P2增加1個(gè)令牌。然后T2就被允許了。當(dāng)它發(fā)生時(shí)，會(huì)從P2移除1個(gè)令牌，給P1增加1個(gè)令牌。顯然，這個(gè)Petri網(wǎng)將會(huì)永遠(yuǎn)重復(fù)這個(gè)循環(huán)。
下面那個(gè)例子更加有趣。T1被允許然后發(fā)生，有效地移動(dòng)1個(gè)令牌給P2。在這個(gè)時(shí)候，T1仍然是唯一被允許的變遷（T2被允許需要P2有2個(gè)令牌）。T1再次發(fā)生，在P1剩下1個(gè)令牌，P2中有2個(gè)令牌?，F(xiàn)在，T1和T2都被允許。假設(shè)T2發(fā)生，從P2移除2個(gè)令牌，給P3增加1個(gè)令牌?，F(xiàn)在T1和T3都被允許。直到?jīng)]有變遷被允許，你應(yīng)該能看到在9次變遷發(fā)生后，在P2僅留下1個(gè)令牌。（注意到，如果當(dāng)T1和T2都被允許的時(shí)候，T1代替了T2發(fā)生，這個(gè)結(jié)果也同樣是在9次變遷發(fā)生后。）
在這個(gè)問(wèn)題中，你將會(huì)被給出1個(gè)或多個(gè)Petri網(wǎng)的描述。對(duì)于每個(gè)描述，你將要模擬NF（0 < NF < 1000）次變遷的發(fā)生，然后輸出留在庫(kù)所里的令牌數(shù)量。如果這個(gè)Petri網(wǎng)在NF次變遷發(fā)生之前就死了，你將按事實(shí)輸出。
這里有2個(gè)例子：
在上面的第一個(gè)Petri網(wǎng)中，有2個(gè)庫(kù)所（P1 和 P2）和2個(gè)變遷（T1 和 T2）。P1初始有1個(gè)令牌。P2沒(méi)有令牌。P1是變遷T1的輸入庫(kù)所，P2是T1的輸出庫(kù)所。在第二個(gè)例子中，有3個(gè)庫(kù)所和3個(gè)變遷，P1有3個(gè)令牌。T2有2個(gè)輸入庫(kù)所，2個(gè)都是P2。
一個(gè)Petri網(wǎng)的操作
每個(gè)Petri網(wǎng)的變遷要么被允許，要么不被允許。一個(gè)變遷被允許當(dāng)且僅當(dāng)每個(gè)輸入庫(kù)所都至少有1個(gè)令牌。任何被允許的變遷可以發(fā)生。如果有多個(gè)變遷被允許，任何一個(gè)都可能發(fā)生。當(dāng)一個(gè)變遷發(fā)生時(shí)，每個(gè)輸入庫(kù)所都會(huì)移除1個(gè)令牌，每個(gè)輸出庫(kù)所都會(huì)增加1個(gè)令牌。這會(huì)有效地利用原子能來(lái)完成，作為一個(gè)事件。如果沒(méi)有一個(gè)變遷被允許，這個(gè)Petri網(wǎng)就被認(rèn)為是死的。
最上面那個(gè)例子，只有T1是被允許的。當(dāng)它發(fā)生時(shí)，會(huì)從P1移除1個(gè)令牌，給P2增加1個(gè)令牌。然后T2就被允許了。當(dāng)它發(fā)生時(shí)，會(huì)從P2移除1個(gè)令牌，給P1增加1個(gè)令牌。顯然，這個(gè)Petri網(wǎng)將會(huì)永遠(yuǎn)重復(fù)這個(gè)循環(huán)。
下面那個(gè)例子更加有趣。T1被允許然后發(fā)生，有效地移動(dòng)1個(gè)令牌給P2。在這個(gè)時(shí)候，T1仍然是唯一被允許的變遷（T2被允許需要P2有2個(gè)令牌）。T1再次發(fā)生，在P1剩下1個(gè)令牌，P2中有2個(gè)令牌?，F(xiàn)在，T1和T2都被允許。假設(shè)T2發(fā)生，從P2移除2個(gè)令牌，給P3增加1個(gè)令牌?，F(xiàn)在T1和T3都被允許。直到?jīng)]有變遷被允許，你應(yīng)該能看到在9次變遷發(fā)生后，在P2僅留下1個(gè)令牌。（注意到，如果當(dāng)T1和T2都被允許的時(shí)候，T1代替了T2發(fā)生，這個(gè)結(jié)果也同樣是在9次變遷發(fā)生后。）
在這個(gè)問(wèn)題中，你將會(huì)被給出1個(gè)或多個(gè)Petri網(wǎng)的描述。對(duì)于每個(gè)描述，你將要模擬NF（0 < NF < 1000）次變遷的發(fā)生，然后輸出留在庫(kù)所里的令牌數(shù)量。如果這個(gè)Petri網(wǎng)在NF次變遷發(fā)生之前就死了，你將按事實(shí)輸出。
輸入
每個(gè)Petri網(wǎng)的描述首先會(huì)包含一個(gè)整數(shù)NP（0 < NP < 100），緊接著有NP個(gè)整數(shù)分別表示編號(hào)為1，2，…，NP的庫(kù)所初始有多個(gè)個(gè)令牌。接著會(huì)有一個(gè)整數(shù)NT（0 < NT < 100）表示變遷的數(shù)量。然后，對(duì)于每個(gè)變遷（編號(hào)為1，2，…，NT）將會(huì)有一個(gè)以0結(jié)尾的整數(shù)序列。序列中的負(fù)數(shù)代表輸入庫(kù)所，所以數(shù)字-n代表有一個(gè)輸入庫(kù)所在n。序列中的正數(shù)代表輸出庫(kù)所，所以數(shù)字p代表有一個(gè)輸出庫(kù)所在p。每個(gè)庫(kù)所至少有一個(gè)輸入庫(kù)所，至少有一個(gè)輸出庫(kù)所。最后，在NT個(gè)變遷的描述之后，會(huì)有一個(gè)整數(shù)代表你至多要模擬變遷發(fā)生的次數(shù)，NF。輸入會(huì)包含一個(gè)或多個(gè)Petri網(wǎng)的描述，最后會(huì)有一個(gè)0。
輸出
對(duì)于每個(gè)Petri網(wǎng)的描述，輸出三行。第一行輸出是第幾組數(shù)據(jù)（從1開(kāi)始連續(xù)編號(hào)）和是否有NF次變遷發(fā)生。如果有，輸出這個(gè)Petri網(wǎng)在NF次變遷發(fā)生后仍然活著。否則輸出這個(gè)Petri網(wǎng)已經(jīng)死了和變遷發(fā)生的次數(shù)。兩種情況下，在第二行都輸出在模擬結(jié)束后，包含1個(gè)或多個(gè)令牌的庫(kù)所的編號(hào)，和每個(gè)這種庫(kù)所含有的令牌數(shù)量。輸出的序列按編號(hào)遞增。每組數(shù)據(jù)的第三行都應(yīng)該是空行。
輸入數(shù)據(jù)將會(huì)被選擇來(lái)保證正確輸出的唯一性。
輸入數(shù)據(jù)將會(huì)被選擇來(lái)保證正確輸出的唯一性。
樣例輸入
2 1 0 2 -1 2 0 -2 1 0 100 3 3 0 0 3 -1 2 0 -2 -2 3 0 -3 1 0 100 0
樣例輸出
Case 1: still live after 100 transitions Places with tokens: 1 (1) Case 2: dead after 9 transitions Places with tokens: 2 (1)
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情
比賽公告
前面幾道是簡(jiǎn)單題,后面才是真正的難題