시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 124 | 75 | 52 | 55.914% |
Alice vill dela ett godishalsband med Bob. Halsbandet består av vita och blåa godisar. För att vara rättvis vill Alice dela halsbandet i två delar med lika många godisbitar i varje. Dock gillar Alice de blåa godisarna mycket mer än de vita, och vill därför få så många blåa godisar i sin halva som möjligt.
Vad är det största antalet blåa godisar Alice kan få i sin del, om hon klipper halsbandet optimalt?
Indatan består av en rad med en sträng som beskriver halsbandet. Strängen består endast av bokstäverna B
och V
, och har totalt ett jämnt antal bokstäver.
Skriv ut en rad med ett heltal, det maximala antalet blåa godisar Alice kan få i sin del av halsbandet.
Halsbandet består av högst 1000000 godisar.
BBVVBVVVBB
4
BVBVBVBV
2
BBVBVVVBBVVBBBVBVVBV
6
BBVVBVVVBB har längd 10 så Alice måste dela halsbandet i två delar med 5 godisar i varje. De möjliga delarna hon kan få är BBVVB, BVVBV, VVBVV, VBVVV, BVVVB, VVVBB, VVBBB, VBBBB, BBBBV, BBBVV. Hon får mest blåa godisar genom att välja VBBBB eller BBBBV som har $4$ blåa godisar.
Figure 1. Ett av två optimala sätt att klippa i exempelfall 1
Olympiad > Swedish Olympiad in Informatics > 2020 > Online Qualification B번