P6424 [COCI 2008/2009 #2] SETNJA

In a binary tree: - Each node has two children: a left child and a right child. - If a node is labeled with an integer $x$, then its left child is labeled $2x$, and its right child is labeled $2x+1$. - The root of the tree is labeled $1$. We traverse the binary tree starting from the root. Each step of the traversal is either jumping to the left child, jumping to the right child, or pausing to rest (staying at the same node). The traversal process is described by a string consisting of the characters `L`, `R`, and `P`. - `L` means jump to the left child. - `R` means jump to the right child. - `P` means pause for one step. The value of $walk$ is the label of the node we finally reach. For example, the $walk$ value of `LR` is $5$, and the $walk$ value of `RPP` is $3$. A traversal is described by `L`, `R`, `P`, and `*`. Each `*` can be any of the three actions. For example, `L*R` may represent `LLR`, `LRR`, and `LPR`. The set `**` may represent `LL`, `LR`, `LP`, `RL`, `RR`, `RP`, `PL`, `PR`, and `PP`. Finally, the total value of $walk$ for such a traversal is the sum of the $walk$ values of all possible concrete traversals represented by it. Compute the total value of $walk$ for the given traversal description.

One line containing a string that describes the traversal.

One line containing an integer, the total value of $walk$.

#### Constraints - For $30\%$ of the testdata, the input string contains no `*` characters. - For $50\%$ of the testdata, the input string contains at most three `*` characters. - For $100\%$ of the testdata, the input string length is less than $10000$, and each character is only one of `L`, `R`, `P`, `*`. #### Notes - This problem is translated from [COCI2008-2009](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #2](https://hsin.hr/coci/archive/2008_2009/contest2_tasks.pdf) SETNJA. Translator: @[mnesia](https://www.luogu.com.cn/user/115711). Translated by ChatGPT 5