e-olymp 8666. Коровий котильон

Задача

В коровьем котильоне — причудливом танце весны — участвуют коровы (обозначаются $ «\gt»$) и быки (обозначаются $ «\lt»$), они кланяются друг другу во время танца. Схематически обозначим пару кланяющихся животных следующим образом: $ «\gt \lt»$. Иногда вторая пара скота может находиться между кланяющейся парой: $ «\gt \gt \lt \lt»$.

Иногда и большее количество коров и быков встречается на танцевальной площадке: $ «\gt \gt \lt \lt \gt \lt»$ (имеется вторая пара кланяющихся коров справа). Сложные аранжировки могут быть совершенно легальными танцевальными образованиями:

Фермер Джон замечает, что бездомная корова иногда пробирается в группу и разбалансирует ее: $ «\gt \gt \lt \lt \lt \lt»$. Это строго запрещено; Фермер Джон хочет наказать нарушителей.

Фермер Джон скопировал данные о том, как $500$ коров участвуют в танцевальной линии, и задался вопросом, правильно ли уравновешена танцевальная линия (то есть весь скот может быть спарен как минимум одним способом чтобы правильно кланяться друг другу). Он скопировал только направление, в котором кланялась каждая корова, без каких-либо лишних пробелов, чтобы можно было определить, какая корова какому быку кланяется. Строки похожи на пример из предыдущего абзаца: «>><&lt». Фермер Джон хочет чтобы Вы написали программу, определяющую правильность танцевальной линии.

Фермер Джон имеет $n$ записей танца $P_{i}$ состоящих из символов $ «\gt»$ и $ «\lt»$;’ различной длины $K_{i} (1 \leqslant K_{i} \leqslant 200)$. Выведите «legal» для тех строк, которые содержат правильные пары кланяющихся коров и «illegal» иначе.

Входные данные

Первая строка содержит одно число $n$ $(1 \leqslant n \leqslant 1000)$. Каждая из следующих $n$ строк содержит число и строку из $K$ символов $ «\gt»$ и $ «\lt»$: $K_{i}$и $P_{i}$.

Выходные данные

Выведите в каждой строке «legal» или «illegal» в зависимости от того, содержит ли соответствующая входная строка допустимую конфигурацию.

Тесты

Входные данные Выходные данные
1 2
6 >><<><
4 ><<>
legal

illegal

2 3
8 <>><><><
6 ><>><<
9 >><>><<><
illegal
legal
illegal
3 5
4 ><><
10 >>><<>><<<
8 >><<<>><
3 >><
12 ><>><>>><<<<
legal
legal
illegal
illegal
legal

Код

 

Решение

Пара начинается с коровы и каждой из них должен соответствовать один бык, стоящий после неё. Для того, чтобы проверить правильность танцевальной линии, будем фиксировать количество встречающихся коров, а при встрече быка это число уменьшать. Отрицательное значение показывает на наличие быка без пары. В таком случае баланса уже не будет и проверять дальше смысла нет.  В случае конечного результата $0$, в линии соблюден баланс — у каждого есть своя пара.

Ссылки

5 thoughts on “e-olymp 8666. Коровий котильон

    • Вы делаете две проверки. На ‘<‘ и отдельно на ‘>’. Зачем? Там же нет третьего варианта! Если не ‘<‘, значит’>’.
    • Правильные отступы нужно сделать в любом случае.
    • В пояснении вы ставите точку с запятой там, где по должна быть точка, а двоеточие ставите вместо тире.
  1. Хорошо, принято. Но как-то у вас все запутано. Я бы это записал так:

Добавить комментарий