Deans Cup
Турнир за Купата на Декана, 2011
Time Limit: 0.3s, Memory Limit: 128MiB
Някои от вас може и да не знаят, но Турнирът за Купата на Декана има две различни издания – едно по математика и едно по информатика. Но кой от двамата шампиони е Истинският Носител на Купата? За да се определи това, по време на награждаването има допълнителна игра. Победителят от нея се обявява за абсолютен шампион и носител на Купата на Декана.
В началото на играта пред играчите и журито има редица от бели и черни билярдни топки. На всяка стъпка от играта се повтарят следните действия:
Ели е стигнала до финала (от страна на информатиците). Помогнете ѝ да спечели купата, като напишете програма, която по дадена първоначалната редица от топки изчислява отговора.
В началото на играта пред играчите и журито има редица от бели и черни билярдни топки. На всяка стъпка от играта се повтарят следните действия:
- Взема се най-лявата топка от редицата, показва се на журито и се премахва от редицата.
- Ако премахнатата топка е била бяла, се обръща редът на останалите топки (тоест последната става първа, предпоследната става втора и т.н.).
- Ако премахнатата топка е била черна, се сменят цветовете на останалите топките (тоест всяка бяла топка става черна и всяка черна става бяла).
- Когато не останат топки в редицата, играта приключва.
Ели е стигнала до финала (от страна на информатиците). Помогнете ѝ да спечели купата, като напишете програма, която по дадена първоначалната редица от топки изчислява отговора.
Вход
На стандартния вход ще бъдат зададени две цели числа N и M, следвани от стринг с N букви, които са 'W' или 'B', обозначаващи, съответно, бяла или черна топка. Повторете този стринг M пъти за да получите първоначалната редица от топки.
Изход
На стандартния изход изведете едно цяло число – броя черни топки, които ще бъдат показани на журито.
Ограничения
- 1 ≤ N ≤ 2,000
- 1 ≤ M ≤ 100,000
Примерен Вход | Примерен Изход |
---|---|
5 2 BWWBW | 7 |
13 101 WBWBWWWWBWBBW | 803 |
В първия пример началната редица е "BWWBWBWWBW". След първия ход тя става "BBWBWBBWB" (първата топка е премахната, а цветът на всяка от следващите е сменен). След втория ход редицата е "WBWBWWBW" (отново същите действия). След третия ход редицата става "WBWWBWB" (първата топка е премахната, а останалите са обърнати наобратно). Остатъка от играта протича с редиците: "BWBWWB", "BWBBW", "BWWB", "BBW", "WB", "B". По време на играта са взети 7 черни топки – на първия, втория, петия, шестия, седмия, осмия и десетия ход.