Best Actress Award
All submissions for this problem are available.
There was tough competition between Amy Adams and Cate Blanchett for Best Actress Award in Oscars 2014. The Oscar Committee decided to choose the one who wins the below game.
The game rules are described as follows:
1)Amy will play first.
2)Each actress can remove 1,K or L characters from the beginning of a given string during each move.
3)The actress who obtains lexicographically Mth smallest string after doing operation (2) will be declared as winner.
If given string is already Mth smallest string,then second actress wins as first actress cannot perform operation 2).
Given the values of K ,L and M and a string S,your task is to tell who wins the game. As both the actresses are intelligent and are eager to win the award, they play the game optimally.
The first line of the input contains an integer T denoting the number of test cases.
The description of T test cases follows in 3T lines.
The first line of each test case contains the integers K and L.
The second line contains a string S consisting of only lowercase [a-z] alphabets.
The third line contains the rank M.
For each test case, output a single line containing A if Amy wins else print B if Blanchett wins.
- 1 ≤ T ≤ 10
- 1 < K < L < 10
- 1 ≤ |S| ≤ 100000
- 1 ≤ M ≤ |S|
Input: 1 2 3 abcdefg 5 Output: B
5th smallest string obtained by removing letters from beginning is efg.
If Amy removes 1,2 or 3 letters from beginning Blanchett can remove 3,2 or 1 letters in turn in order to obtain efg.Thus Blanchett wins.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, GO|
Fetching successful submissions
If you are still having problems, see a sample solution here.