Cheerio Contest 3 P2 - Double-O-Seven

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

You are playing a game of "Double-O-Seven" with your friend. In the game, both players start with an ammo count and a score of 0. The game is played in N rounds. In a round, both players simultaneously choose one of three actions:

  1. R Reload: The player increases their ammo count by 1.

  2. F Fire:

    If the player's ammo count is 0, firing does nothing.

    If the player's ammo count is greater than 0, then:

    • Decrease the player's ammo count by 1.
    • Decrease the opponent's score by 1.
    • Increase the player's score by 1.
  3. B Block: Restrict both players' score from increasing or decreasing this round.

Your friend is so confident that he could beat you, that he will tell you all his actions beforehand. What is the maximum score you could get, knowing your opponent's actions?


Points Awarded N Additional Constraints
2 points 1 \le N \le 10^3 The opponent never fires
3 points 1 \le N \le 10^3 None
10 points 1 \le N \le 10^6 None

Input Specification

The first line contains a single integer N.

The second line contains a string of length N consisting of the characters RFB. The ith character in the string indicates the action your friend will make on the ith round of the game.

Output Specification

Output the maximum possible score you can obtain if you played optimally.

Sample Input 1


Sample Output 1


Explanation for Sample Output 1

A possible sequence of actions that obtains this score is RBF.

On the first round, both players reload and have an ammo count of 1.

On the second round, your friend fires and decreases their ammo count to 0. Since you blocked, both players still have a score of 0.

On the third round, your friend does nothing as they fired with an ammo count of 0. Since you fired, you now have a score of 1 and an ammo count of 0.

Sample Input 2


Sample Output 2


Explanation for Sample Output 2

A possible sequence of actions that obtains this score is RRBFFRFFB.


There are no comments at the moment.