James is currently sitting in his hotel room in a hallway with side-by-side rooms, with the leftmost room being room number 1, and the rightmost being room number . He is currently on a school trip, and he has just pissed off one of his friends, Alex, by exposing him in their group chat.
Alex is currently on his way to James's room to have a "friendly conversation" with James.
James knows the room numbers of all of his friends, but he has no clue which of these rooms belongs to Alex; nevertheless, he wants to prolong the distance that Alex has to travel to get to his room.
James, being the extrovert he is, can request to hide in any of the rooms in the hallway (since he knows basically everyone in the school), and he has enough time to move to one of these rooms. (He can't leave the hallway, however, since there are teachers stationed on either side of the hallway that prevents students from leaving.)
Since James does not actually know which of the rooms belongs to Alex, he will assume the worst case scenario: He will treat all of his friends' rooms as Alex's room, and he will always assume that Alex will choose the correct direction to head in to find the room James is hiding in. He will then figure out how long (on average) Alex will need to get to him by calculating the average distance it takes Alex to travel from any of the rooms to his current room. He will then choose the room that Alex will take the longest distance to get to on average to hide in.
Which room should James hide in?
Constraints
Input Specification
The first line will contain two space-separated integers, and .
The second line will contain letters. G
is a room that doesn't contain one of James's friends, and B
is a room that does contain one of James's friends.
Output Specification
Output one number, the room number of the room James should hide in. (Assume room numbers start from 1)
If there exists multiple, output the room with the highest room number.
Sample Input
7 3
GBGGBBG
Sample Output
1
Sample Output Explanation
Let's do some casework:
If James chooses room 1, the first room that Alex can be in is room 2, which is only 1 room away. The second room that Alex can be in is room 5, which is 4 rooms away. The third room that Alex can be in is room 6, which is 5 rooms away. On average, Alex will need (1+4+5)/3, whih is 10/3 rooms to get to James.
If James chooses room 2, the first room that Alex can be in is also room 2, which is 0 rooms away. The second room that Alex can be in is room 5, which is 3 rooms away. The third room that Alex can be in is room 6, which is 4 rooms away. On average, Alex will need (0+3+4)/3, whih is 7/3 rooms to get to James.
Following the logic for all 7 rooms, we see that the average distance for each room is:
Room 1: 10/3
Room 2: 7/3
Room 3: 2
Room 4: 5/3
Room 5: 4/3
Room 6: 5/3
Room 7: 8/3
Therefore, the answer is Room 1.
Comments