TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

Description

平行運算是一種運算形式,其中很多指令都是同步進行的。平行運算的可行性建立在一個原則之上:大的問題幾乎總是可以分成一些較小的問題,而這些較小的問題是可以同時(平行)解決的。目前有幾種不同形式的平行計算中:bit-level parallelism增加CPU每次處理的資料大小、instruction level parallelism將數個CPU指令同時運行、data parallelism同時處理不同區域的資料、task parallelism則以不同性質的工作做平行化。平行運算已經存在高速運算的領域中多年,但是近年來由於材料的物理性質限制了CPU時脈的提升,它開始受到相當的重視。事實上,來自多核心處理器的流行,平行運算是當前最主要的運算架構。

平行運算的程式比普通「順序」程式更難寫,因為平行化代來了幾種新的潛在軟體缺陷以及硬體影響,例如隨著平行的數量增加,電力消耗、散熱、程式間通訊、資料同步等等問題。其中最常見的問題是競賽條件(racing condition)。

競賽條件又分兩大類:
■ 讀/寫互斥(Read-Write conflict)是指有兩個指令對同一筆資料一個要讀一個要寫,但是沒有強制規定誰先執行的情況下,每次執行時讀出的資料可能不同,通常這不是原設計希望的行為。
■ 寫/寫互斥(Write-Write conflict)是指有兩個指令對同一筆資料都要寫入,但是同樣沒有強制規定誰先執行。此後如果有一個指令要讀入此筆資料,但是在此之前這筆資料又不一定會被覆寫的話,每次執行時讀出的資料就可能不同,這同樣是要避免的。但是如果之後沒有再讀到這筆資料,就不算互斥。

現在給你一個程式,它的指令可能會被平行、甚至交換順序執行。程式中用一些開關控制指令的先後順序。每個開關一開始都是關閉的,只有一個預設的開關「o」是開啟的。程式中的指令有:
■ Read:寫作「 R var s1 s2 」,表示當 s1 這個開關打開時就準備讀入 var 這個變數,但是平行運算的排程不保證會立刻執行它。在執行結束後才會把 s2 打開。
■ Write:寫作「 W var s1 s2 」,表示當 s1 這個開關打開時就準備寫入 var 這個變數,但是平行運算的排程不保證會立刻執行它。在執行結束後才會把 s2 打開。
■ Join:寫作「 J s1 s2 s3 」。s1,s2,s3都是開關,當 s1 和 s2 都打開時,s3 就會被打開。(這個動作因為可以直接以硬體實作,因此可以視為是及時完成的,但是就算 s3 被打開,那些要等到 s3 打開才能做的指令也不保證會立刻執行。)

Input Format

輸入檔中會有多個程式,每個程式的開頭佔一行,有兩個數字 n,m 表示有多少個指令和多少個變數。接下來一行變數定義,共有 m 個以空白隔開的字串。接著有 n 行,每行都是前述 Read,Write或是Join指令。變數以及開關名最多 15 個字,都是小寫英文字母。每個指令最後的那個開關一定是之前沒有出現過的(也不會是「o」),其他的開關一定是「o」或是之前出現過的。0 ≦ n ≦ 1000,0 ≦ m ≦ 100。

Output Format

對每個程式輸出一行。如果程式中有出現「讀/寫互斥」或「寫/寫互斥」則輸出「Potential racing condition found」,否則輸出「Racing free」。

Sample Input 1

2 1
aa
R aa o a
R aa o b
2 1
aa
R aa o a
W aa o b
4 1
aa
W aa o a
W aa o b
J a b c
R aa c d
3 2
aa bb
W aa o a
W aa o b
R bb b c
0 0

Sample Output 1

Racing free
Potential racing condition found
Potential racing condition found
Racing free

Hints

Problem Source

原TIOJ1486 / NPSC2007決賽(prob B)

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 65536 262144 1