## Cheerio Contest 1 S5 - Coin Game

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type

Instead of writing your ICS4U final exam, your CS teacher Mr. G challenges you to a puzzle! He has laid out a line of coins numbered from to on a table, where each coin is either heads or tails. In one move, you can choose any coin that is currently heads and flip it to become tails. Your score is then increased by the length of the contiguous subsequence of tails created by that move. In order to pass the course get a good mark, Mr. G asks you to determine the maximum possible score that can be obtained after performing a sequence of moves. Can you satisfy his request?

#### Constraints

• will not exceed the number of heads in the initial setup.
• There is at least one coin that is initially heads.
Points Awarded
2 points
4 points
9 points

#### Input Specification

The first line contains a string of length . The character of the string denotes the initial state of the coin, with H representing heads and T representing tails.

The second line contains one integer .

#### Output Specification

Output the maximum score that can be obtained.

#### Sample Input

THTTHH
3

#### Sample Output

15

#### Explanation for Sample Output

The optimal solution is to flip coins , and (in that order). This sequence of moves obtains points.