PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author:
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Toofan is playing a game containing N rings. Each ring can be either swished or passed.
The game ends when either all N rounds have been played, and X swishes have been achieved; or it’s impossible for Toofan to obtain X swishes from the following rings.
You’re given a string S of length M, denoting Toofan’s moves till the game ended. Find the value of N.
EXPLANATION:
Let ct denote the number of swishes Toofan obtained over the course of the game.
Then,
- If ct \geq X, the game must have ended with Toofan clearing all N rings.
- So, in this case the answer is just M - we know the full game.
- Otherwise, ct \lt X and the game must have ended when it became clear that it’s impossible for Toofan to win any more, no matter what he does.
- This means there are not enough rings remaining for Toofan to reach X swishes.
He has ct swishes right now, so if there are at least another X - ct rings, he can possibly swish them all and reach X.
So, there must be strictly less than X - ct more rounds remaining - meaning the maximum we can do is X - ct - 1. - Adding this to the existing number of rings M gives us the answer, that being M + (X - ct - 1).
- This means there are not enough rings remaining for Toofan to reach X swishes.
TIME COMPLEXITY:
\mathcal{O}(M) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
m, k = map(int, input().split())
s = input()
swish = s.count('S')
if swish >= k: print(m)
else: print(m + (k - 1 - swish))