## COCI '08 Contest 2 #5 Setnja

View as PDF

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem type

In an infinite binary tree:

• Each node has exactly two children – a left and a right child.
• If a node is labeled with the integer , then its left child is labeled and its right child .
• The root of the tree is labeled .

A walk on the binary tree starts in the root. Each step in the walk is either a jump onto the left child, onto the right child, or pause for rest (stay in the same node).

A walk is described with a string of letters L, R and P:

• L represents a jump to the left child;
• R represents a jump to the right child;
• P represents a pause.

The value of the walk is the label of the node we end up on. For example, the value of the walk LR is , while the value of the walk RPP is .

A set of walks is described by a string of characters L, R, P and *. Each * can be any of the three moves; the set of walks contains all walks matching the pattern.

For example, the set L*R contains the walks LLR, LRR and LPR. The set ** contains the walks LL, LR, LP, RL, RR, RP, PL, PR and PP.

Finally, the value of a set of walks is the sum of values of all walks in the set.

Calculate the value of the given set of walks.

### Input Specification

A string describing the set. Only characters L, R, P and * will appear and there will be at most of them.

#### Output Specification

Output the value of the set.

#### Scoring

In test data worth points, there will be no characters *. In test data worth points, there will be at most three characters *.

#### Sample Input 1

P*P

#### Sample Output 1

6

#### Sample Input 2

L*R

#### Sample Output 2

25

#### Sample Input 3

**

#### Sample Output 3

33

#### Sample Input 4

LLLLLRRRRRLLLLLRRRRRLLLLLRRRRRLLLLL

#### Sample Output 4

35400942560