Correct Incorrect Predictions
Elections are getting closer and people have started speculating who is
going to be their next PM. The media is also involved and it starts conducting
opinion polls in all the constituencies. In one such opinion poll which is done
for the Bharatiya Java Party (BJP), the media lists all the constituencies in
alphabetical order, conducts surveys and then reports the results as a string
of W's and L's. A W indicates that the BJP is winning that constituency
and an L indicates the it is losing it.
Shri Chaiwala, the PM candidate for BJP is however not very happy with the
opinion polls. He feels that the media is biased towards the other parties and
has intentionally given incorrect results. So he calls for a press conference
and quotes that "The media has not given correct predictions. They have
generated the results using a fake program. This program can give the correct
results for atmost P consecutive constituency and incorrect results for
atmost Q consecutive constituency."
Your task is to help Shri Chaiwala find the maximum number of constituency
they could win if the predictions can have atmost P consecutive correct
results and atmost Q consecutive incorrect results.
The first line of the input consists of the number of cases (T). T test
cases follows. Each test case has 2 lines. The first line contains 2 numbers P
and Q separated by a space. The next line contains a string of W's and L's
which is the prediction given by the media.
For each test case, output a single line containing the maximum number of
seats that BJP could win.
T ≤ 50
1 ≤ P, Q ≤ 100
1 ≤ |prediction string| ≤ 100
3 2 2 WW 2 2 WWWW 1 1 WL
2 3 2
Lets denote C for a Correct prediction and I for an Incorrerct prediction.
- In the first case, P and Q are 2. So you can have atmost 2 consecutive
correct and atmost 2 consecutive incorrect predictions. The possible strings
are CC, CI, IC, II. If we apply these strings on the predictions, then the
seats BJP can win are - 2 (CC), 1 (CI) , 1 (IC) and 0 (II). Therefore the
answer is 2.
- In the second case, we can get 2 seats by applying 2 correct predictions
anywhere. However we can get 3 by using CCIC.
- If we use CI, because the first prediction is correct, BJP wins 1 seat and because the second prediction is incorrect( i.e. L is incorrect there) so they win that seat too. So answer is 2.
|Time Limit:||0.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, GO|
Fetching successful submissions