Setnja

무한 이진 트리에서:

• 각 노드에는 자식이 정확히 둘, 즉 왼쪽 자식과 오른쪽 자식이 있다.
• 어떤 노드에 정수 \(X\)가 적혀 있으면, 왼쪽 자식에는 \(2 \cdot X\), 오른쪽 자식에는 \(2 \cdot X + 1\)이 적혀 있다.
• 트리의 루트에는 \(1\)이 적혀 있다.

이진 트리에서의 산책은 루트에서 시작한다. 산책의 각 단계는 왼쪽 자식으로 점프, 오른쪽 자식으로 점프, 또는 잠깐 쉬기(같은 노드에 머무르기) 중 하나이다.

산책은 글자 L, R, P의 문자열로 나타낸다:

• L은 왼쪽 자식으로의 점프;
• R은 오른쪽 자식으로의 점프;
• P는 쉬기.

산책의 값은 마지막에 도착한 노드에 적힌 수이다. 예를 들어 산책 LR의 값은 \(5\)이고, 산책 RPP의 값은 \(3\)이다.

산책들의 집합은 문자 L, R, P, *의 문자열로 나타낸다. 각 *는 세 가지 이동 중 어느 것이든 될 수 있으며, 산책 집합은 패턴에 들어맞는 모든 산책을 포함한다.

예를 들어 집합 L*R는 산책 LLR, LRR, LPR를 포함한다. 집합 **는 산책 LL, LR, LP, RL, RR, RP, PL, PR, PP를 포함한다.

마지막으로, 산책 집합의 값은 집합에 있는 모든 산책의 값의 합이다.

주어진 산책 집합의 값을 계산하시오.

집합을 나타내는 문자열이 주어진다. 문자 L, R, P, *만 나타나며 최대 \(10000\)개이다.

집합의 값을 출력한다.

채점: 전체 점수의 \(30\%\)에 해당하는 테스트 데이터에는 문자 *가 없다. 전체 점수의 \(50\%\)에 해당하는 테스트 데이터에는 문자 *가 최대 세 개 있다.

riseoj 작성

출처 COCI 2008/2009 Contest 2