Farmer John, desperate to win the award for best cow photographer at the county
fair, is trying to take the perfect photograph of his \(N\) cows
(\(2 \leq N \leq 2\cdot 10^5\), \(N\) even).

Farmer John owns cows of two potential breeds: Guernseys and Holsteins.
To make his photo as aesthetic as possible, he wants to line up his
cows so that as many Guernseys are in even-numbered positions in the line
as possible (the first position in the line is an odd position, the next is
an even position, and so on). Due to his lack of strong
communication with his cows, the only way he can achieve his goal is by asking
even length "prefixes" of his cows to reverse themselves (a prefix
consists of the range of cows from the first cow up to the \(j\)th cow
for some position \(j\)).

Please count the minimum number of reversals required for Farmer John to achieve
his goal.

Problem credits: Aryansh Shrivastava

SCORING

• Test cases 2-6 satisfy \(N\le 1000\).
• Test cases 7-11 satisfy no additional constraints.

Problem credits: Aryansh Shrivastava

The first line of input contains the value of \(N\).

The second line contains a string of length \(N,\) specifying the initial ordering
of the cows from left to right. Each 'H' represents a Holstein, while each 'G'
represents a Guernsey.

Output the minimum number of reversals needed on a single line.

riseoj 작성

출처 올림피아드 > USACO > 2021-2022 > US Open > Bronze