29783번 - 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, $\mathbf{T}$. $\mathbf{T}$ lines follow. Each line represents a test case and contains a string $\mathbf{C}$. The $i$-th character of $\mathbf{C}$ represents the original choice of the $i$-th person in clockwise order using an uppercase R to mean rock, an uppercase P to mean paper, and an uppercase S to mean scissors.

출력

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the minimum number of changes that are required such that no two neighbors end up with the same choice.

제한

• 1ドル \le \mathbf{T} \le 100$.
• Each character of $\mathbf{C}$ is either an uppercase R, an uppercase P, or an uppercase S.

서브태스크 1 (9점)

• 3ドル \le$ the length of $\mathbf{C} \le 10$.

서브태스크 2 (20점)

• 3ドル \le$ the length of $\mathbf{C} \le 1000$.

힌트

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.