prithivMLmods/Coder-Stat

1 2<h1><font color="#000000">Problem C:</font> How can I satisfy thee? Let me count the ways...</h1>3<!-- end en only -->4 5<!-- begin en only -->6<p>7Three-valued logic is a logic system that has, in addition to "true" and 8"false", "unknown" as a valid value.  9 10In the following, logical values "false", "unknown" and "true" are 11represented by 0, 1 and 2 respectively. 12</p><p>13Let "-" be a unary operator (i.e. a symbol representing one argument function) 14and let both "*" and "+" be binary operators (i.e. symbols representing 15two argument functions). 16These operators represent negation (NOT), conjunction (AND) and 17disjunction (OR) respectively. 18These operators in three-valued logic can be defined in Table C-1.19</p>20<!-- end en only -->21 22<CENTER>23<!-- begin en only -->24Table C-1: Truth tables of three-valued logic operators25<!-- end en only -->26<br>27<TABLE>28<TR align=center><TD>-X</TD><TD></TD><TD>(X*Y)</TD><TD></TD><TD>(X+Y)</TD><TR>29<TR><TD><img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_2008C1"></TD><TD></TD>30    <TD><img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_2008C2"></TD><TD></TD>31    <TD><img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE1_2008C3"></TD> <TD></TD></TR>32</TABLE>33</CENTER>34 35 36<!-- begin en only -->37<p>38Let P, Q and R be variables ranging over three-valued logic values. 39For a given formula, you are asked to answer the number of triples (P,Q,R) 40that satisfy the formula, that is, those which make the value of the 41given formula 2. 42A formula is one of the following form (X and Y represent formulas). 43</p>44<ul>45<li> Constants: 0, 1 or 246<li> Variables: P, Q or R47<li> Negations: -X48<li> Conjunctions: (X*Y)49<li> Disjunctions: (X+Y)50</ul>51<p>52Note that conjunctions and disjunctions of two formulas are always 53parenthesized. 54</p>55<!-- end en only -->56<p>57<!-- begin en only -->58For example, when formula (P*Q) is given as an input, the value of 59this formula is 2 when and only when (P,Q,R) is (2,2,0), (2,2,1) or (2,2,2). 60Therefore, you should output 3. 61<!-- end en only -->62</p>63 64 65<h3>Input</h3>66<!-- begin en only -->67<p>68The input consists of one or more lines. Each line contains a formula. 69A formula is a string which consists of 0, 1, 2, P, Q, R, -, *, +, (, ). 70Other characters such as spaces are not contained. 71The grammar of formulas is given by the following BNF. 72</p>73<!-- end en only -->74 75<pre>76&lt;formula&gt; ::= 0 | 1 | 2 | P | Q | R |77              -&lt;formula&gt; | (&lt;formula&gt;*&lt;formula&gt;) | (&lt;formula&gt;+&lt;formula&gt;)78</pre>79 80<!-- begin en only -->81<p>82All the formulas obey this syntax and thus you do not have to care about 83grammatical errors.84Input lines never exceed 80 characters.  85</p><p>86Finally, a line which87contains only a "." (period) comes, indicating the end of the input.88</p>89<!-- end en only -->90 91 92 93 94<h3>Output</h3>95<!-- begin en only -->96<p>97You should answer the number (in decimal) of triples (P,Q,R) that make the 98value of the given formula 2.  One line containing the number should be 99output for each of the formulas, and no other characters should be output.100</p>101<!-- end en only -->102 103 104 105<h3>Sample Input</h3>106<PRE>107(P*Q)108(--R+(P*Q))109(P*-P)11021111112(-1+(((---P+Q)*(--Q+---R))*(-R+-P)))113.114</PRE>115 116<h3>Output for the Sample Input</h3>117<PRE>11831191112001212712201237124</PRE>125 126 127 128 129 130