Logical Expression

AtCoder

IDabc189_d

Time2000ms

Memory256MB

Difficulty—

Given are $N$ strings $S_1,\ldots,S_N$, each of which is `AND` or `OR`. Find the number of tuples of $N+1$ variables $(x_0,\ldots,x_N)$, where each element is $\text{True}$ or $\text{False}$, such that the following computation results in $y_N$ being $\text{True}$: * $y_0=x_0$; * for $i\geq 1$, $y_i=y_{i-1} \land x_i$ if $S_i$ is `AND`, and $y_i=y_{i-1} \lor x_i$ if $S_i$ is `OR`. Here, $a \land b$ and $a \lor b$ are logical operators. ## Constraints * $1 \leq N \leq 60$ * $S_i$ is `AND` or `OR`. ## Input Input is given from Standard Input in the following format: $N$ $S_1$ $\vdots$ $S_N$ [samples]

Samples

Input #1

2
AND
OR

Output #1

5

For example, if $(x_0,x_1,x_2)=(\text{True},\text{False},\text{True})$, we have $y_2 = \text{True}$, as follows:

*   $y_0=x_0=\text{True}$
*   $y_1=y_0 \land x_1 = \text{True} \land \text{False}=\text{False}$
*   $y_2=y_1 \lor x_2 = \text{False} \lor \text{True}=\text{True}$

All of the five tuples $(x_0,x_1,x_2)$ resulting in $y_2 = \text{True}$ are shown below:

*   $(\text{True},\text{True},\text{True})$
*   $(\text{True},\text{True},\text{False})$
*   $(\text{True},\text{False},\text{True})$
*   $(\text{False},\text{True},\text{True})$
*   $(\text{False},\text{False},\text{True})$

Input #2

5
OR
OR
OR
OR
OR

Output #2

63

All tuples except the one filled entirely with $\text{False}$ result in $y_5 = \text{True}$.

API Response (JSON)

{
  "problem": {
    "name": "Logical Expression",
    "description": {
      "content": "Given are $N$ strings $S_1,\\ldots,S_N$, each of which is `AND` or `OR`. Find the number of tuples of $N+1$ variables $(x_0,\\ldots,x_N)$, where each element is $\\text{True}$ or $\\text{False}$, such tha",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc189_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given are $N$ strings $S_1,\\ldots,S_N$, each of which is `AND` or `OR`.\nFind the number of tuples of $N+1$ variables $(x_0,\\ldots,x_N)$, where each element is $\\text{True}$ or $\\text{False}$, such tha...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments