XAndOr

Problem code: INSOMA5

All submissions for this problem are available.

The planet of XANDOR was famous in the intergalactic empire for being home to the Carden - a race of super-intelligent computer scientists that were held in high regard for their achievements in the Intergalactic Mind Game Olympiads. The Carden decided to build a huge computer to answer questions related to Life, the Universe and Everything. They decided to use only their best two-input, noise immune, Boolean gates for this device - AND, OR and XOR. After a lot of minimization, they arrived at a variable assignment for their gates. Just then, lightning struck and erased all the parentheses from their expression. Not willing to spend the trouble parenthesizing the huge expression again, they outsourced the work to Earth.

As a consultant to XANDOR, you need to create a computer program that parenthesizes the Boolean expression in such a manner that the expression results in a true value and report the number of ways possible to do it. In case it is not possible to do so, you need to return 0.

Input

An unparenthesized Boolean expression containing literals T and F which are connected via gates represented as . (dot) for an AND gate, + (plus) for an OR gate and * (star) for an XOR gate. There will be at least one literal in input line. Maximum number of literals i.e. T or F will be 15.

Output

Line 1: A single value C >= 0 representing the number of true parenthesizations possible.

Example

Input:
T.F+T*F

Output:
5

Description
The 5 values correspond to the parenthesizations (((T.F)+T)*F), ((T.F)+(T*F)), ((T.(F+T))*F, (T.((F+T)*F)), (T.(F+(T*F))) - all of which evaluate to true.

Author: admin
Date Added: 19-03-2009
Time Limit: 2 - 9 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

This is a standard DP

vivek.cs.iitr @ 25 Sep 2010 11:27 AM

This is a standard DP problem. I am doin everything right, yet getting a wrong answer. Can someone provide a good test case for it ?

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

HELP

Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

 

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • If you are still having problems, see a sample solution here.

CodeChef is a global programming communityCodeChef hosts online programming competitions