루미 알고리즘

#1456골드Brickor

PO 2018 학교 예선코딩출제 Fredrik Ekholm스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Karin har hittat på ett ensamspel som spelas med Othello-brickor, vilka är svarta på ena sidan och vita på andra sidan. Hon lägger ut en rad med brickor, som var och en kan vara svart eller vit. Målet är att få alla brickor att ha den vita sidan uppåt.

Ett “drag” är att “plocka ut” ett intilliggande par av brickor någonstans ur sekvensen, vända på dem (vit blir svart, svart blir vit), och lägga tillbaka dem antingen i början av raden eller i slutet av raden, utan att ändra parets inbördes ordning.

Skriv ett program som, givet den ursprungliga raden av brickor, skriver ut det minsta antalet drag som behövs för att göra alla brickor vita.

(그림은 원문 저장소에서 볼 수 있습니다)

En möjlig dragsekvens i exempel 2

Indata

Indata består av en sträng med enbart bokstäverna S och V. Strängen är mellan 3 och 15 tecken lång.

Utdata

Skriv ut ett enda tal: det minsta antalet drag som behövs för att göra alla brickor vita. För givna testdata kommer det alltid vara möjligt att nå målet.

Poängsättning

För testfall värda 60 poäng är strängens längd högst 10, och svaret är högst 6. För testfall värda 40 poäng gäller inga speciella begränsningar.

예제

예제 1

입력
SVVSVVV
출력
2

예제 2

입력
VSVSSSVVVV
출력
4

출처 표기

출처: Programmeringsolympiaden 2018년 학교 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.