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

В коровьем котильоне – причудливом танце весны – участвуют коровы (обозначаются “>”) и быки (обозначаются “<”), они кланяются друг другу во время танца. Схематически обозначим пару кланяющихся животных следующим образом: “> <”. Иногда вторая пара скота может находиться между кланяющейся парой: “> > < <”.

Иногда и большее количество коров и быков встречается на танцевальной площадке: “> > < < > <” (имеется вторая пара кланяющихся коров справа). Сложные аранжировки могут быть совершенно легальными танцевальными образованиями:

Фермер Джон замечает, что бездомная корова иногда пробирается в группу и разбалансирует ее: “> > < < < <”. Это строго запрещено; Фермер Джон хочет наказать нарушителей.

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

Фермер Джон имеет n записей танца p_i состоящих из символов ‘>’ и ‘<’ различной длины k_i (1 ≤ k_i ≤ 200). Выведите “legal” для тех строк, которые содержат правильные пары кланяющихся коров и “illegal” иначе.

Вход. Первая строка содержит одно число n (1 ≤ n ≤ 1000). Каждая из следующих n строк содержит число и строку из k символов ‘>’ и ‘<’: k_i и p_i.

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

Пример входа	Пример выхода
2 6 >><<>< 4 ><<>	Legal illegal

РЕШЕНИЕ

структуры данных - стек

Анализ алгоритма

Промоделируем стек следующим образом:

· При поступлении коровы ‘>’ положим в стек символ ‘>’.

· При поступлении быка ‘<’ извлечем корову из стека (соответствующие корова и бык образуют кланяющуюся друг другу пару). Если при поступлении быка стек пустой, то рассматриваемая конфигурация не является допустимой.

По окончанию обработки входной строки стек должен быть пустым. Для каждой коровы должен найтись соответствующий ей танцевальный бык.

Данная задача эквивалента задаче о корректности скобочной записи. Рассмотрим скобочную запись с одним типом скобок: ‘(‘ и ‘)’. Например “( ( ) ) ( )”, или “( ( ) ) ) (”. Требуется определить, является ли заданная скобочная запись корректной.

Реализация алгоритма

Читаем входные данные. Последовательно обрабатываем тесты.

cin >> tests;

while (tests--)

{

cin >> k >> p;

Изначально считаем входную строку корректной, утсановим flag = 0. Инициализируем пустой стек: cnt = 0.

flag = 0; cnt = 0;

Обрабатываем k символов строки.

for (i = 0; i < k; i++)

{

При обработке символа ‘>’ совершаем операцию push, При обработке ‘<’ совершаем pop.

if (p[i] == '>') cnt++; else cnt--;

Если в некоторый момент времени количество операций pop больше числа операций push, то текущая строка некорректная. Устанавливаем flag = 1.

if (cnt < 0) { flag = 1; break; }

}

Выводим ответ. Конфигурация является допустимой, если стек пустой (cnt = 0) и flag = 0.

if (cnt == 0 && flag == 0)

puts("legal");

else

puts("illegal");

}

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int tests = con.nextInt();

while(tests-- > 0)

{

int k = con.nextInt();

String p = con.next();

int flag = 0, cnt = 0;

for (int i = 0; i < k; i++)

{

if (p.charAt(i) == '>') cnt++; else cnt--;

if (cnt < 0) { flag = 1; break; }

}

if (cnt == 0 && flag == 0)

System.out.println("legal");

else

System.out.println("illegal");

}

con.close();

}

}

Python реализация

Читаем входные данные. Последовательно обрабатываем тесты.

tests = int(input())

for _ in range(tests):

k, p = input().split()

k = int(k)

Изначально считаем входную строку корректной, утсановим flag = 0. Инициализируем пустой стек: cnt = 0.

flag = cnt = 0

Обрабатываем k символов строки.

for i in range(k):

При обработке символа ‘>’ совершаем операцию push, При обработке ‘<’ совершаем pop.

if p[i] == '>': cnt += 1

else: cnt -= 1

Если в некоторый момент времени количество операций pop больше числа операций push, то текущая строка некорректная. Устанавливаем flag = 1.

if cnt < 0:

flag = 1;

break

Выводим ответ. Конфигурация является допустимой, если стек пустой (cnt = 0) и flag = 0.

if cnt == 0 and flag == 0:

print("legal")

else:

print("illegal")