2013年7月12日 星期五

11103 - WFF 'N PROOF

Problem D: WFF 'N PROOF

WFF 'N PROOF 是一個藉由骰子玩的邏輯遊戲,骰子的六面分別有可能有的字符 K, A, N, C, E, p, q, r, s, t。Well-formed formula (WFF) 定義為一個符合以下規則的字串:
  • p, q, r, s, t  都屬於 WFFs
  • 如果 w 屬於 WFF, 則 Nw 屬於WFF
  • 如果 wx 屬於 WFFs, 則 Kwx, Awx, Cwx, Ewx 也都屬於 WFFs.
WFF 字串的意思解釋如下:

  • p, q, r, s, t 是 0 (false) 或 1 (true) 的邏輯代數。
  • K, A, N, C, E 分別表示 and(&), or(|), not(!), implies(→), equals(==),真值表如下:
Definitions of K, A, N, C, and E
     w  x   Kwx   Awx    Nw   Cwx   Ewx
  1  1   1   1    0   1   1
  1  0   0   1    0   0   0
  0  1   0   1    1   1   0
  0  0   0   0    1   1   1

tautology (恆真式) 在 WFF 中,不管邏輯代數的值為何,計算出來值皆為 1 (true)。
例如
ApNp 是恆真式,p and (not p) 代入 p = 0 or p = 1 都是 1 (true)。
ApNq 不是恆真式,因為當 p = 0, q = 1 計算得到 0 (false)

現在從骰子中得到一些字符,想要使用這些得到最長的 WFF 字串。


輸入有多筆測資,每組只會有一行長度不超過 100 的字串,最後一組有一個 0 不用處理。

對於每組測資,輸出一個最長的 WFF。如果有多組解,任何一組都可以。如果無法湊出任合一組,輸出 "no WFF possible",不包括雙引號。

Sample Input

qKpNq
KKN
0

Possible Output for Sample Input

KqNq
no WFF possible

Gordon V. Cormack