#P12950. [GCJ Farewell Round #1] Untie
[GCJ Farewell Round #1] Untie
题目描述
A group of people are sitting in a circle, playing a special version of rock, paper, scissors. In this game, each person chooses rock, paper, or scissors in secret and then everyone reveals their choice to everyone else. Each person then compares their selection to their two neighbors, and can win, lose, or tie against each of them independently. The only way to tie is when both people make the same choice.
You want to make it so that no game is a tie. For each player, you can let them keep their choice, or you can ask them to change to any of the other two options (you choose to which one). What is the minimum number of people you need to request a change from to ensure that there are no ties between neighbors after those changes are made?
输入格式
The first line of the input gives the number of test cases, . lines follow. Each line represents a test case and contains a string . The -th character of represents the original choice of the -th person in clockwise order using an uppercase to mean rock, an uppercase to mean paper, and an uppercase to mean scissors.
输出格式
For each test case, output one line containing Case # , where is the test case number (starting from 1) and is the minimum number of changes that are required such that no two neighbors end up with the same choice.
3
PRSSP
RRRRRRR
RSPRPSPRS
Case #1: 2
Case #2: 4
Case #3: 0
提示
Sample Explanation
In Sample Case #1, there is a pair of neighbors that both chose paper (the first and last character of the input) and another pair that both chose scissors. Therefore, we need at least two changes. One way of doing it with two changes is to change the leftmost paper to scissors and the rightmost scissors to rock, to obtain SRSRP.
In Sample Case #2, all 7 participants chose rock. If we change at most 3 selections, there will be at least 4 remaining rocks, and at least two of them will be neighbors. Therefore, the minimum number of changes is at least 4. One way to achieve exactly 4 is to get PRSRPRS.
In Sample Case #3, no pair of neighbors tied, so no changes are needed.
Limits
- .
- Each character of is either an uppercase , an uppercase , or an uppercase .
Test Set 1 (9 Pts, Visible Verdict)
- the length of .
Test Set 2 (20 Pts, Visible Verdict)
- the length of .