Đường đi trên cây

View as PDF

Submit solution


Points: 0.48 (partial)
Time limit: 0.6s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho một cây tam phân đầy đủ, mỗi nút có đúng ~3~ nút con: nút con trái, nút con giữa và nút con phải. Mỗi nút ghi một số nguyên theo quy tắc sau:

  • Nút gốc ghi số ~1~.
  • Nếu một nút ghi số ~X~ thì nút con trái của nó ghi số ~3X~, nút giữa ghi số ~3X + 1~, nút phải ghi số ~3X + 2~.

image

Để di chuyển trên cây từ một nút người ta dùng một trong ~4~ lệnh sau:

  • ~L~: Di chuyển đến nút con trái,
  • ~C~: Di chuyển đến nút con giữa,
  • ~R~: Di chuyển đến nút con phải,
  • ~S~: Đứng nguyên tại nút hiện thời.

Một khuôn mẫu đường đi từ nút gốc là một xâu gồm các ký tự: 'L', 'C', 'R', 'S' và '*' trong đó dấu '*' có thể được thay thế bởi ~1~ trong ~4~ ký tự: 'L', 'C', 'R' và 'S'.

Với một cách thay thế dấu '*' ta nhận được một đường đi từ nút gốc tới một nút lá nào đó và tổng các số ghi trên các nút đi qua gọi là trọng số của đường đi đó. Cho một khuôn mẫu đường đi, hãy tính tổng ~T~ trọng số các đường đi phù hợp với khuôn mẫu.

Input

Chứa một xâu không quá 2000 ký tự 'L', 'C', 'R', 'S' và '*'.

Output

Ghi ra file văn bản số ~T~ tìm được.

Sample Input

*LS

Sample Output

55

Comments

Please read the guidelines before commenting.


There are no comments at the moment.