Решение задачи Злые школьники с Codeforces

Без пояснения   Просмотров: 66

В ЛКШ.Зима день экскурсий, поэтому t групп школьников отправились в Торжок. Тротуары в Торжке настолько узкие, что идти приходится в колонне по-одному.

Изначально некоторые из школьников злы. Для удобства будем описывать группу школьников строкой из заглавных латинских букв «A» и «P»:

«A» соответствует злому школьнику
«P» соответствует спокойному школьнику
Строка описывает школьников от последнего к первому, слева направо.

Каждую минуту каждый злой школьник кидает снежок в спину идущего непосредственно перед ним.

Формально, если злой школьник соответствует символу заданной строки с индексом i, то снежок он будет кидать в школьника, который соответствует символу с индексом i+1 (студенты в строке заданы от последнего к первому!). Если школьник, в которого попали снежком, еще не был зол, то он становится злым. Даже если первый (самый правый в строке) школьник является злым, он не бросает снежок, так как впереди него нет другого ученика.


Рассмотрим первый тестовый пример. В нем колонна изначально имеет такой вид: PPAP. Через минуту единственный злой школьник кинет снежок в школьника, идущего перед ним, и он тоже станет злым: PPAA. После этого, новых злых школьников появляться не будет.

Помогите преподавателям ЛКШ.Зима определить для каждой группы время, спустя которое в ней появится последний злой школьник.

Код 

#include <iostream>
 
using namespace std;
 
int main()
{
    //APAPAPAPPPA
    int t;
    cin >> t;
    for(int i = 0; i < t; ++i){
        int n;
        string s;
        cin >> n >> s;
        int res = 0;
        int pos = s.find('P');
        while(pos + 1){
            bool b = false;
            for(int j = 0; j < s.size(); ++j){
                if(s[j] == 'P' && s[j - 1] != 'A')
                    s[j] = '-';
                else if(s[j] == 'P' && s[j - 1] == 'A'){
                    s[j] = 'A';
                    b = true;
                    int temp = s.find('A', j + 1);
                    if(temp < 0)
                        j = s.size();
                    else
                        j = temp;
 
                }
            }
            pos = s.find('P');
            if(b)
                ++res;
        }
        cout << res << " ";
    }
 
    return 0;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 HSECODES [email protected] Карта сайта