루미 알고리즘

#1379골드Konamikoden

PO 2016 지역 대회코딩출제 Johan Sannemo스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

Problem

En vanlig fuskkod i många gamla spel är den så kallade konamikoden, som består av sekvensen upp upp ned ned vänster höger vänster höger B A.

Du håller på att programmera ett spel, där du vill lägga in ett fusk som aktiveras när man skriver in konamikoden. Dock vill du göra det med en twist - det ska vara tillåtet att trycka på högst K andra knappar mellan din konamikod.

Om K = 3 betyder detta att vi får sätta in tre extra knapptryckningar. Alltså skulle upp upp ned vänster ned vänster B B höger vänster höger B A vara en korrekt konamikod, där de tre extra knapptryckningarna är markerade i fetstil.

Du ska nu skriva ett program som, givet en sekvens av knapptryckningar, avgör det lägsta K-värde som behövs för att konamikoden ska förekomma i sekvensen. Notera att knapptryckningar som sker före den första konamikodstryckningen och efter den sista konamikodstryckningen inte räknas. Detta betyder att för sekvensen B B vänster upp upp ned vänster ned vänster B B höger vänster höger B A A B upp ska vi fortfarande svara K = 3.

Indata

Indata innehåller en enda rad med N tecken - sekvensen av knapptryckningar. Den kommer ges som en sekvens av bokstäverna U, N, V, H, B, A, som står för knapptryckningarna upp, ned, vänster, höger, B, A.

Det är garanterat att konamikoden finns som en delsekvens av knapptryckningarna.

Utdata

Du ska skriva ut en enda rad med heltalet K som beskrivet i uppgiften.

Poäng

  • 7 poäng N ≤ 11.
  • 11 poäng N ≤ 100.
  • 12 poäng N ≤ 3000.
  • 20 poäng N ≤ 200000.

예제

예제 1

입력
UUNNVHVHBA
출력
0

예제 2

입력
UUNVNVBBHVHBA
출력
3

예제 3

입력
UUNNVHBVHBA
출력
1

출처 표기

출처: Programmeringsolympiaden 2016년 지역 대회 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.