James is in Danger

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

James is currently sitting in his hotel room in a hallway with N side-by-side rooms, with the leftmost room being room number 1, and the rightmost being room number N. 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 M 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 N 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 M 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 M 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

2\le N\le 1\times 10^5

1\le M \le N

Input Specification

The first line will contain two space-separated integers, N and M.

The second line will contain N 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

There are no comments at the moment.