Problemas
사람들이 원형으로 앉아 가위바위보의 특별한 버전을 하고 있다. 이 게임에서 각 사람은 바위, 보, 또는 가위를 비밀리에 선택한 뒤, 모두가 서로의 선택을 공개한다. 그 다음 각 사람은 자신의 선택을 양옆 두 이웃과 각각 비교하며, 각 이웃에 대해 독립적으로 이기거나 지거나 비길 수 있다. 비기는 경우는 두 사람이 같은 선택을 했을 때뿐이다.
어떤 게임도 무승부가 되지 않게 만들고 싶다. 각 플레이어에 대해, 원래 선택을 그대로 두거나, 다른 두 선택지 중 하나로 바꾸도록 요청할 수 있다(어느 것으로 바꿀지는 당신이 정한다). 변경이 모두 반영된 뒤 이웃 사이에 무승부(즉 같은 선택)가 하나도 없도록 하기 위해 최소 몇 명에게 변경을 요청해야 하는가?
Entrada
입력의 첫 줄에는 테스트 케이스 개수 R은 바위, 대문자 P는 보, 대문자 S는 가위를 의미한다.
Salida
각 테스트 케이스마다 한 줄을 출력하라. 형식은 Case #이며,
여기서
Ejemplo
3
PRSSP
RRRRRRR
RSPRPSPRS
Case #1: 2
Case #2: 4
Case #3: 0
샘플 케이스 #1에서는 이웃한 두 사람이 모두 종이(P)를 선택한 쌍(입력의 첫 문자와 마지막 문자)과 이웃한 두 사람이 모두 가위(S)를 선택한 쌍이 있다. 따라서 최소 두 번의 변경이 필요하다. 두 번의 변경으로 가능한 한 방법은 왼쪽 끝의 종이를 가위로 바꾸고 오른쪽 끝의 가위를 바위로 바꿔 SRSRP를 만드는 것이다.
샘플 케이스 #2에서는 7명이 모두 바위를 선택했다. 최대 3개만 바꾸면 여전히 바위가 최소 4개 남고, 그중 적어도 두 명은 이웃하게 된다. 따라서 필요한 변경 횟수의 최소는 4 이상이다. 정확히 4번으로 만드는 한 방법은 PRSRPRS이다.
샘플 케이스 #3에서는 이웃한 쌍이 비기는 경우가 없으므로 변경이 필요 없다.
Fuente
GCJ 2023a E
Debes iniciar sesión para escribir código.