Canadian Computing Competition: 2013 Stage 2, Day 1, Problem 2
Don Cherry has been hired to run 24-hour coverage of a series of single-elimination, bracket-style, furniture disassembly tourneys (tournaments). Each competitor has a furniture disassembly skill level, an integer between and
. In every head-to-head match, the competitor with the larger skill level wins and moves on, while the other is eliminated from the tourney. It is guaranteed that, at any time, the skill levels of all competitors are distinct, so there are no ties.
There are
competitor positions in the tourney tree, numbered
from left to right. In the first round, competitors
and
face off in a furniture disassembly race, as do competitors
and
, etc. In each subsequent round, the winners of the first two matches from the previous round compete, as do the winners of the following two, etc. After
rounds, a single winner remains. For example, when
, the tourney tree looks like this:
where represents the winner of the match between competitors
and
,
represents the winner of the match between competitors
and
, and
represents the winner of the match between
and
. The winner of this tourney is
.
Because of sponsorship contracts, some competitors will be replaced over time. After any new person comes in, a new tourney is held.
In order to help Don Cherry, you must write a program to compute certain tourney statistics at various points in time, given a sequence of
commands — see the input format below.
Input Specification
The first line of input contains two integers,
and
, separated by one space.
The next lines, for
from
to
, each contain one integer
, indicating the skill level of the initial competitor at position
in the tourney tree.
Each of the following lines will be a command in one of three formats:
means that the competitor at position
is removed, and replaced with a new one with skill level
. A tourney should then be held.
means that your program should determine who won the current tourney. Print the position
(between
and
) of this competitor.
means that your program should print out the number of rounds that the competitor at position
won in the current tourney.
Output Specification
For each or
command in the input, print out the corresponding integer on a line by itself.
Sample Input
2 8
30
20
10
40
S 1
W
R 4 9
S 4
W
R 2 35
S 2
W
Sample Output
1
4
0
1
2
2
Explanation
The results of the initial tourney are as follows:
As can be seen, competitor wins
match, and competitor
wins the entire tourney. After this, competitor
is replaced by a new competitor with skill level
. As can be seen below, this causes a different outcome for the tourney held after the third command:
Finally, the state of the tourney tree after the next competitor replacement (caused by the sixth command) is:
Comments