#P12950. [GCJ Farewell Round #1] Untie

    ID: 12752 Type: RemoteJudge 10000ms 2048MiB Tried: 0 Accepted: 0 Difficulty: 3 Uploaded By: Tags>动态规划 DP贪心2023Google Code Jam

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

输出格式

For each test case, output one line containing Case # x:yx: y, where xx is the test case number (starting from 1) and yy 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

  • 1T1001 \leq \mathbf{T} \leq 100.
  • Each character of C\mathbf{C} is either an uppercase R\mathbf{R}, an uppercase P\mathbf{P}, or an uppercase s\mathbf{s}.

Test Set 1 (9 Pts, Visible Verdict)

  • 33 \leq the length of C10\mathbf{C} \leq 10.

Test Set 2 (20 Pts, Visible Verdict)

  • 33 \leq the length of C1000\mathbf{C} \leq 1000.