堆
测试数据来自 system/1522
描述
这里的堆是一个无限大的二叉树,它具有性质:
每一个结点有且仅有两个子节点:左、右子节点;
每个结点都有个数字标号。根节点标号为1;
如果一个结点的标号为X,则它的左子节点标号为2*X,右子节点标号为2*X+1。
一次在堆上的行走由根出发,经过多次步骤组成,每个步骤用一个字母表示:'L'或'R'或'P'。
'L'表示跳到左子节点;
'R'表示跳到右子节点;
'P'表示暂停一次;
行走结束时,最后所停在的节点上的标号就是这次行走的价值。比如:行走LR的价值是5、RPP的价值是3。
一类行走的集合可以用字符'L','R','P'或'*'组成的字符串表示,一个'*'字符表示这次步骤有'L','R'或'P'三种选择。这个集合由所有可能的行走组成。比如:
集合:L*R,包括3个行走:LLR,LRR和LPR。
集合:**,包括:LL,LR,LP,RL,RR,RP,PL,PR,PP。
现在要求出给定的一个集合中,所有可能行走的价值之和。
格式
输入格式
一个长度不超过10000的字符串,仅由'L','R','P'和'*'4种字符组成。
输出格式
要求的价值和。
样例1
样例输入1
L*R
样例输出1
25
样例2
样例输入2
**
样例输出2
33
限制
各个测试点1s
提示
50%的输入数据中,'*'不超过3个。
来源
2009芜湖市集训队