Ljepotica
레이팅 미적용의견: 0
Croatian Olympiad in Informatics 2019.
Page 4 of 9
Beauty and the Geek is a reality television series advertised as connecting female beauties and male geeks
with the goal of creating "The Ultimate Social Experiment". This task is advertised as connecting reality
TV and competitive programming with the goal of creating a fun task.
Our hero is a beauty Ena, trapped in a complete binary tree of depth N. Each node of the tree has a
value: root of the tree has a value of 1, and for each node with a value of \(x\), its left child has a value of
2x, and its right child has a value of 2\(x + 1\). Ena can move from a node to one of its two children,
heading for the exit which is located in one of the leaves (nodes of depth N, with no children).
Ena knows an exact path from the root to the exit leaf. More precisely, she knows the correct sequence
of N – 1 moves, each of them being “left“ or “right“, which would guide her from the root to the exit
leaf. Unfortunately, Ena is not sure which side is left and which side is right. Therefore, during her trip,
she changed her mind exactly K times about the meaning of “left” and “right”. When she changes her
mind, she moves accordingly until the end of the trip (a leaf node) or until the next change of mind.
Ena's change of mind can happen only once before each move in the tree (including the first one).
Also, nobody knows whether Ena had correct sides in mind while entering the root of the tree.
The producers of the TV show will save the lost Ena if you, her geek partner, answer correctly to the
following question: What is the sum of leaf values where Ena can finish her trip, considering only leaves
with values of at least A and at most B?
subtask
points
additional constraints
1
8
\(K = 0\)
2
14
\(N \le 25\)
3
17
A is the smallest, and B is the greatest value
where Ena can finish
4
61
no additional constraints
(See examples on the next page.)
Croatian Olympiad in Informatics 2019.
Page 5 of 9
The first line contains integers N and K from the task description (\(2 \le N \le 1000\), \(0 \le K \le N\) – 1).
In the second line there is a word containing N – 1 characters ‘L’ (left) and ‘R’ (right) representing the
correct path from the root to the exit leaf.
The third line contains the number A from the task description, in binary form without leading zeros.
The fourth line contains the number B from the task description, in binary form without leading zeros.
Ena will be able to finish in leaves A and B.
Output the required sum as a decimal integer modulo 1 000 000 007.
3 0
LR
101
110114 2
LRR
1010
1110375 2
RLLR
10010
1011182
First sample description: Ena will never change her mind, but we don't known if she had the correct
left/right sides in mind from the beginning. So, she might have followed the instructions correctly and
go to the left, and then the right child. Or, she might have followed the inverse instructions, going first
to the right child and then to the left child. The arriving leaves have values 5 and 6 which correspond to
A and B, so the answer is 5 + 6.
Second sample description: Possible Ena's paths: (left, left, left), (left, left, right), (left, right, left),
(right, left, right), (right, right, left), or (right, right, right).평가 및 의견
Ljepotica
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Ljepotica