2013-07-12 13:27:21Morris
[UVA][greedy] 11103 - WFF 'N PROOF
Problem D: WFF 'N PROOF
WFF 'N PROOF is a logic game played with dice. Each die has six faces representing some subset of the possible symbols K, A, N, C, E, p, q, r, s, t. A Well-formed formula (WFF) is any string of these symbols obeying the following rules:- p, q, r, s, and t are WFFs
- if w is a WFF, Nw is a WFF
- if w and x are WFFs, Kwx, Awx, Cwx, and Ewx are WFFs.
- p, q, r, s, and t are logical variables that may take on the value 0 (false) or 1 (true).
- K, A, N, C, E mean and, or, not, implies, and equals as defined in the truth table below.
|
|
| 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 |
Given a collection of symbols resulting from throwing a set of dice, determine the longest WFF that can be formed from those symbols.
Input consists of several test cases. Each test case is a single line containing a string containing between 1 and 100 of the characters. A line containing 0 follows the last case. For each test case, output a line containing the longest WFF that can be formed using some subset of the letters in the string. If there are several such WFFs, any one will do. If no WFF can be constructed, output a line containing "no WFF possible" as shown below.
Sample Input
qKpNq KKN 0
Possible Output for Sample Input
KqNq no WFF possible
Gordon V. Cormack
題目希望根據語法，找到一組最長的前序式。
可以隨便排列或捨去。
其中可以發現 NOT(N) 可以放在最前面不用管他。這裡就給他 greedy。
其次要計算變數的個數，如果變數個數為 0 輸出不可能。
在 greedy 前，先抽離一個變數放最後，最後將一個變數匹配一個運算子。
#include <stdio.h>
#include <string.h>
using namespace std;
int main() {
char s[105];
while(scanf("%s", s) == 1 && s[0] != '0') {
int val[128], vidx = 0;
int op[128], oidx = 0;
int NOT = 0;
int i, j;
for(i = 0; s[i]; i++) {
if(s[i] >= 'p')
val[vidx++] = s[i];
else if(s[i] == 'N')
NOT++;
else
op[oidx++] = s[i];
}
if(vidx == 0) {
puts("no WFF possible");
continue;
}
for(i = 0; i < NOT; i++)
putchar('N');
for(i = 1, j = 0; i < vidx && j < oidx; i++, j++) {
putchar(op[j]);
putchar(val[i]);
}
putchar(val[0]);
puts("");
}
return 0;
}