Problem D
Slikhalskæde

Halskæden for testgruppe 1

Ane vil dele en slikhalskæde med Bo. Halskæden består af to slags slik med hhv. blåbær- og vaniljesmag. For at det skal være retfærdigt vil Ane dele halskæden i to dele med lige mange stykker slik i hver. Men Ane synes meget bedre om blåbærsmag end om vanilje, og hun vil derfor have så meget blåbærslik i sin halvdel som muligt.

Hvor mange stykker blåbærslik kan Ane maksimalt få i sin halvdel, hvis hun klipper halskæden over optimalt?

Indlæsning

Indlæsningen er en linje bestående af en tegnfølge som beskriver halskæden. Tegnfølgen består af bogstaverne B (for »blåbær«) og V (for »vanilje«), dens totale antal bogstaver er et lige tal.

Udskrift

Udskriv en linje med et enkelt heltal, det maksimale antal stykker blåbærslik, som Ane kan opnå i sin halvdel af halskæden.

Pointgivning

Din løsning køres på tre testgupper. For at få point for en gruppe skal du klare samtlige test i gruppen.

Forklaring af eksempel 1

BBVVBVVVBB har længde 10, så Ane skal dele halskæden i to dele med 5 stykker slik i hver. De mulige dele er BBVVB, BVVBV, VVBVV, VBVVV, BVVVB, VVVBB, VVBBB, VBBBB, BBBBV og BBBVV. Hun får mest blåbærslik ved at vælge VBBBB eller BBBBV, som hver har $4$ stykker med blåbærsmag.

Figure 1: Et af to optimale løsninger til eksempel 1

BBVVBVVVBB

4

BVBVBVBV

2

BBVBVVVBBVVBBBVBVVBV

6