題目 1890:
藍(lán)橋杯算法提高VIP-Petri Net Simulation
時間限制: 2s
內(nèi)存限制: 192MB 提交: 7 解決: 3
題目描述
一個Petri網(wǎng)是一個計(jì)算模型，用來說明并發(fā)事件。每個Petri網(wǎng)包含一些庫所（被表示成圓圈），變遷（被表示成黑色的矩形），和一些有向邊，用來連接庫所到變遷，和變遷到庫所。每個庫所能夠包含0個或多個令牌（被表示成黑點(diǎn)）。
這里有2個例子：
在上面的第一個Petri網(wǎng)中，有2個庫所（P1 和 P2）和2個變遷（T1 和 T2）。P1初始有1個令牌。P2沒有令牌。P1是變遷T1的輸入庫所，P2是T1的輸出庫所。在第二個例子中，有3個庫所和3個變遷，P1有3個令牌。T2有2個輸入庫所，2個都是P2。
一個Petri網(wǎng)的操作
每個Petri網(wǎng)的變遷要么被允許，要么不被允許。一個變遷被允許當(dāng)且僅當(dāng)每個輸入庫所都至少有1個令牌。任何被允許的變遷可以發(fā)生。如果有多個變遷被允許，任何一個都可能發(fā)生。當(dāng)一個變遷發(fā)生時，每個輸入庫所都會移除1個令牌，每個輸出庫所都會增加1個令牌。這會有效地利用原子能來完成，作為一個事件。如果沒有一個變遷被允許，這個Petri網(wǎng)就被認(rèn)為是死的。
最上面那個例子，只有T1是被允許的。當(dāng)它發(fā)生時，會從P1移除1個令牌，給P2增加1個令牌。然后T2就被允許了。當(dāng)它發(fā)生時，會從P2移除1個令牌，給P1增加1個令牌。顯然，這個Petri網(wǎng)將會永遠(yuǎn)重復(fù)這個循環(huán)。
下面那個例子更加有趣。T1被允許然后發(fā)生，有效地移動1個令牌給P2。在這個時候，T1仍然是唯一被允許的變遷（T2被允許需要P2有2個令牌）。T1再次發(fā)生，在P1剩下1個令牌，P2中有2個令牌?，F(xiàn)在，T1和T2都被允許。假設(shè)T2發(fā)生，從P2移除2個令牌，給P3增加1個令牌?，F(xiàn)在T1和T3都被允許。直到?jīng)]有變遷被允許，你應(yīng)該能看到在9次變遷發(fā)生后，在P2僅留下1個令牌。（注意到，如果當(dāng)T1和T2都被允許的時候，T1代替了T2發(fā)生，這個結(jié)果也同樣是在9次變遷發(fā)生后。）
在這個問題中，你將會被給出1個或多個Petri網(wǎng)的描述。對于每個描述，你將要模擬NF（0 < NF < 1000）次變遷的發(fā)生，然后輸出留在庫所里的令牌數(shù)量。如果這個Petri網(wǎng)在NF次變遷發(fā)生之前就死了，你將按事實(shí)輸出。
這里有2個例子：
在上面的第一個Petri網(wǎng)中，有2個庫所（P1 和 P2）和2個變遷（T1 和 T2）。P1初始有1個令牌。P2沒有令牌。P1是變遷T1的輸入庫所，P2是T1的輸出庫所。在第二個例子中，有3個庫所和3個變遷，P1有3個令牌。T2有2個輸入庫所，2個都是P2。
一個Petri網(wǎng)的操作
每個Petri網(wǎng)的變遷要么被允許，要么不被允許。一個變遷被允許當(dāng)且僅當(dāng)每個輸入庫所都至少有1個令牌。任何被允許的變遷可以發(fā)生。如果有多個變遷被允許，任何一個都可能發(fā)生。當(dāng)一個變遷發(fā)生時，每個輸入庫所都會移除1個令牌，每個輸出庫所都會增加1個令牌。這會有效地利用原子能來完成，作為一個事件。如果沒有一個變遷被允許，這個Petri網(wǎng)就被認(rèn)為是死的。
最上面那個例子，只有T1是被允許的。當(dāng)它發(fā)生時，會從P1移除1個令牌，給P2增加1個令牌。然后T2就被允許了。當(dāng)它發(fā)生時，會從P2移除1個令牌，給P1增加1個令牌。顯然，這個Petri網(wǎng)將會永遠(yuǎn)重復(fù)這個循環(huán)。
下面那個例子更加有趣。T1被允許然后發(fā)生，有效地移動1個令牌給P2。在這個時候，T1仍然是唯一被允許的變遷（T2被允許需要P2有2個令牌）。T1再次發(fā)生，在P1剩下1個令牌，P2中有2個令牌?，F(xiàn)在，T1和T2都被允許。假設(shè)T2發(fā)生，從P2移除2個令牌，給P3增加1個令牌?，F(xiàn)在T1和T3都被允許。直到?jīng)]有變遷被允許，你應(yīng)該能看到在9次變遷發(fā)生后，在P2僅留下1個令牌。（注意到，如果當(dāng)T1和T2都被允許的時候，T1代替了T2發(fā)生，這個結(jié)果也同樣是在9次變遷發(fā)生后。）
在這個問題中，你將會被給出1個或多個Petri網(wǎng)的描述。對于每個描述，你將要模擬NF（0 < NF < 1000）次變遷的發(fā)生，然后輸出留在庫所里的令牌數(shù)量。如果這個Petri網(wǎng)在NF次變遷發(fā)生之前就死了，你將按事實(shí)輸出。
輸入格式
每個Petri網(wǎng)的描述首先會包含一個整數(shù)NP（0 < NP < 100），緊接著有NP個整數(shù)分別表示編號為1，2，…，NP的庫所初始有多個個令牌。接著會有一個整數(shù)NT（0 < NT < 100）表示變遷的數(shù)量。然后，對于每個變遷（編號為1，2，…，NT）將會有一個以0結(jié)尾的整數(shù)序列。序列中的負(fù)數(shù)代表輸入庫所，所以數(shù)字-n代表有一個輸入庫所在n。序列中的正數(shù)代表輸出庫所，所以數(shù)字p代表有一個輸出庫所在p。每個庫所至少有一個輸入庫所，至少有一個輸出庫所。最后，在NT個變遷的描述之后，會有一個整數(shù)代表你至多要模擬變遷發(fā)生的次數(shù)，NF。輸入會包含一個或多個Petri網(wǎng)的描述，最后會有一個0。
輸出格式
對于每個Petri網(wǎng)的描述，輸出三行。第一行輸出是第幾組數(shù)據(jù)（從1開始連續(xù)編號）和是否有NF次變遷發(fā)生。如果有，輸出這個Petri網(wǎng)在NF次變遷發(fā)生后仍然活著。否則輸出這個Petri網(wǎng)已經(jīng)死了和變遷發(fā)生的次數(shù)。兩種情況下，在第二行都輸出在模擬結(jié)束后，包含1個或多個令牌的庫所的編號，和每個這種庫所含有的令牌數(shù)量。輸出的序列按編號遞增。每組數(shù)據(jù)的第三行都應(yīng)該是空行。
輸入數(shù)據(jù)將會被選擇來保證正確輸出的唯一性。
輸入數(shù)據(jù)將會被選擇來保證正確輸出的唯一性。
樣例輸入
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)擊這里了解課程詳情