Решение задачи Злые школьники с Codeforces
Без пояснения   Просмотров: 66
В ЛКШ.Зима день экскурсий, поэтому t групп школьников отправились в Торжок. Тротуары в Торжке настолько узкие, что идти приходится в колонне по-одному.
Изначально некоторые из школьников злы. Для удобства будем описывать группу школьников строкой из заглавных латинских букв «A» и «P»:
«A» соответствует злому школьнику
«P» соответствует спокойному школьнику
Строка описывает школьников от последнего к первому, слева направо.
Каждую минуту каждый злой школьник кидает снежок в спину идущего непосредственно перед ним.
Формально, если злой школьник соответствует символу заданной строки с индексом i, то снежок он будет кидать в школьника, который соответствует символу с индексом i+1 (студенты в строке заданы от последнего к первому!). Если школьник, в которого попали снежком, еще не был зол, то он становится злым. Даже если первый (самый правый в строке) школьник является злым, он не бросает снежок, так как впереди него нет другого ученика.
Рассмотрим первый тестовый пример. В нем колонна изначально имеет такой вид: PPAP. Через минуту единственный злой школьник кинет снежок в школьника, идущего перед ним, и он тоже станет злым: PPAA. После этого, новых злых школьников появляться не будет.
Помогите преподавателям ЛКШ.Зима определить для каждой группы время, спустя которое в ней появится последний злой школьник.
Изначально некоторые из школьников злы. Для удобства будем описывать группу школьников строкой из заглавных латинских букв «A» и «P»:
«A» соответствует злому школьнику
«P» соответствует спокойному школьнику
Строка описывает школьников от последнего к первому, слева направо.
Каждую минуту каждый злой школьник кидает снежок в спину идущего непосредственно перед ним.
Формально, если злой школьник соответствует символу заданной строки с индексом i, то снежок он будет кидать в школьника, который соответствует символу с индексом i+1 (студенты в строке заданы от последнего к первому!). Если школьник, в которого попали снежком, еще не был зол, то он становится злым. Даже если первый (самый правый в строке) школьник является злым, он не бросает снежок, так как впереди него нет другого ученика.
Рассмотрим первый тестовый пример. В нем колонна изначально имеет такой вид: PPAP. Через минуту единственный злой школьник кинет снежок в школьника, идущего перед ним, и он тоже станет злым: PPAA. После этого, новых злых школьников появляться не будет.
Помогите преподавателям ЛКШ.Зима определить для каждой группы время, спустя которое в ней появится последний злой школьник.