SETNJA - Setnja

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/setnja


Trong một cây nhị phân vô hạn:

  • Mỗi nút có đúng 2 con – một con trái và một con phải.
  • Nếu một nút được gán nhãn bằng số nguyên X, thì con trái của nó được gán nhãn 2*X và con phải của nó được gán nhãn 2*X+1.
  • Gốc của cây được gán nhãn 1.

Một cuộc dạo chơi trên cây nhị phân bắt đầu từ gốc. Tại mỗi bước, ta sẽ nhảy tới con trái hoặc con phải của nút hiện thời, hoặc là dừng lại tại chính nút đó để nghỉ.

Một cuộc dạo chơi được mô tả bằng một chuỗi các chữ cái 'L', 'R' và 'P':

  • 'L' thể hiện bước nhảy tới con trái;
  • 'R' thể hiện bước nhảy tới con phải;
  • 'P' thể hiện việc dừng để nghỉ.

Giá trị của một cuộc dạo chơi là nhãn của nút mà chúng ta kết thúc. Ví dụ, giá trị của cuộc dạo chơi LR là 5, trong khi giá trị của cuộc dạo chơi RPP là 3.

Một tập hợp các cuộc dạo chơi được mô tả bởi một chuỗi các kí tự 'L', 'R', 'P' và '*'. Mỗi dấu '*' có thể là một trong 3 cách di chuyển; tập hợp các cuộc dạo chơi chứa tất cả các cuộc dạo chơi thích hợp với khuôn mẫu đó.

Ví dụ, tập hợp L*R chứa các cuộ dạo chơi LLR, LRR và LPR. Tập hợp ** chứa các cuộ dạo chơi LL, LR, LP, RL, RR, RP, PL, PR và PP.

Cuối cùng, giá trị của một tập hợp các cuộc dạo chơi đúng bằng tổng các giá trị của tất cả các cuộc dạo chơi trong tập hợp đó.

Tính giá trị của một tập hợp các cuộc dạo chơi cho trước.

Input

Một chuỗi mô tả tập hợp. Chỉ có các kí tự 'L', 'R', 'P' and '*' xuất hiện trong chuỗi, và có nhiều nhất 10000 kí tự.

Output

Ghi giá trị của tập hợp đó.

Example

Input:
L*R

Output:
25

Được gửi lên bởi:Race with time
Ngày:2008-11-16
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:COCI 2008-2009

hide comments
2021-05-27 18:04:14
Tham khảo: https://vnspoj.github.io/problems/SETNJA
2017-12-18 10:10:18
BigNum base = 10^9 ae cẩn thận
2017-11-22 02:12:17
sao ko số lớn là một tội ác :)))
2016-08-03 05:07:07
Code tối ưu thì để int64 vẫn AC nhé :)
2016-08-02 10:40:01
viết sai số lớn làm mất 1 hit :(
2016-07-29 05:48:51 Phong
vkl đổi sang Qword hết tle ... Quỳ ..
2016-07-02 12:27:06 Nguyễn Vĩnh Thịnh
cảm ơn comment qword
bạn đã cứu rỗi mình =))
2016-04-23 05:21:13
QHD mà sao vẫn không AC :=((
2016-01-03 10:00:47 Prismatic
để qword tránh tle :v
2015-05-13 09:46:13 Stupid Dog
bó tay với TLE, chỉ còn cách dùng BigInteger Java
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.