1960: [USACO 2022 US Open Contest Bronze] Problem 1. Photoshoot
文件提交：无需freopen
内存限制：256 MB
时间限制：2.000 S
评测方式：普通裁判
命题人：
提交：5
解决：1
题目描述
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≤N≤2⋅105, 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 ).
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.
输入
The first line of input contains the value of N.
输出
Output the minimum number of reversals needed on a single line.
样例输入
14
GGGHGHHGHHHGHG样例输出
1提示
In this example, it suffices to reverse the prefix consisting of the first six cows.
GGGHGHHGHHHGHG (Before)
-> HGHGGGHGHHHGHG (After)
Before the reversal, four Guernseys were at even positions. After the reversal, six Guernseys are at even positions. It is impossible for there to be more than six Guernseys at even positions.