## COCI '08 Contest 2 #5 Setnja

View as PDF

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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