OpenKattis
Skånemästerskapen 2016

Start

2016-01-30 09:30 CET

Skånemästerskapen 2016

End

2016-01-30 14:30 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -3229 days 21:34:48

Time elapsed

5:00:00

Time remaining

0:00:00

Problem C
Konamikoden

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

  1. $N \le 11$.

  2. $N \le 100$.

  3. $N \le 3000$.

  4. $N \le 200\, 000$.

Sample Input 1 Sample Output 1
UUNNVHVHBA
0
Sample Input 2 Sample Output 2
UUNVNVBBHVHBA
3
Sample Input 3 Sample Output 3
UUNNVHBVHBA
1