Ввод 1 Вывод 1 Ввод 2 Вывод 2
6 No 24
([ ()) ] { [ () ([ ] { }) [ ] ] ({ } { { } }) }[] Yes
Эта задача – первая в серии задач, где рассматриваются скобочные выражения. Она знакомит с понятием правильного скобочного выражения. Скобочное выражение является правильным, если у каждой открывающей скобки есть своя закрывающая скобка соответствующего типа, а внутри этой пары скобок находится правильное скобочное выражение.
Рассмотрим использование стека для проверки такого скобочного выражения
[ ([ ] { }) [ ] ] (). В стеке будем хранить открытые и до сих пор не закрытые скобки в порядке их открытия.
В схеме над стрелками, показано какая скобка обрабатывается в данный момент. Вертикальные столбики скобок показывают состояние стека, самая нижняя скобка та, которая попала в стек первой, она будет извлечена последней, а самая верхняя та, которая попала последней к текущему моменту и будет извлечена первой.
Скобочное выражение является неправильным в трёх случаях:
1. Очередной является закрывающая скобка, а стек пуст (не осталось открывающих).
2. Тип очередной закрывающей не совпадает с типом последней открытой скобки.
3. После обработки всего выражения в стеке остались открывающие скобки.
Детали реализации:
1. Реализуем стек в виде символьного массива и одного целого числа, которое обозначает размер стека в данный момент.
2. 100 000 элементов – это много, но нам столько и ненужно. Достаточно массива на 50 000. А если в какой-то момент открывающих скобок стало 50 001, то можно выводить ответ No.
Program skobki;
Var stek: array [1..50001] of char;
n, i, vs: longint;
sk: char;
Begin
assign(input,' bracket.in ');
assign(output,' bracket.out ');
reset(input);
rewrite(output);
readln(n);
if n mod 2<>0 then
Begin
write('No'); close(output); halt;
end;
vs:=0;
for i:=1 to n do
Begin
read(sk);
if (sk='(') or (sk='[') or (sk='{') then
begin vs:=vs+1; stek[vs]:=sk; continue; end;
if (vs=50001) then
begin write('No'); close(output); halt; end;
if ( (sk=')') or (sk=']') or (sk='}') ) and (vs=0) then
begin write('No'); close(output); halt; end;
if ((sk=')') and (stek[vs]='(')) or
((sk=']') and (stek[vs]='[')) or
((sk='}') and (stek[vs]='{'))
then vs:=vs-1
else begin write('No'); close(output); halt; end;
end;
if vs=0 then write('Yes')
else write('No');
close(input);
close(output);
End.
Задача 1 «Новогодний балл»
Ввод данных — из файла input.txt Ограничение по памяти — 64 мегабайта
Вывод данных — в файл output.txt Ограничение времени — 1 секунда на тест
Петя был приглашен на ежегодный новогодний бал, который организован администрацией школы, в которой он учится. Поскольку такое приглашение поступило Пете впервые, то он решил изучить правила главного школьного танца.
Пусть «<» обозначает парня, а «>» - девушку. Тогда правильной расстановкой танцующих назовем такую расстановку, в которой для каждой девушки можно найти «незанятого» пария, находящегося только справа от нее и нет такой девушки, для которой не было бы найдено пары.
Например, расстановка «>>>><<><<><><><<» будет правильной, что иллюстрирует следующий рисунок:
Из рисунка видно, что девушка «занимает» того парня, который находится ближе к ней и не является «занятым» кем-то ранее. При этом девушки «занимают» тех парной, которые находятся наиболее близко к ним, если идти слева направо, т.е. девушка номер 4 на рисунке займет парня номер 5 раньше, чем девушка номер 3.
Расстановка «>><<<>><» является неправильной, т.к. девушка, которая располагается на позиции 6, не может найти себе «незанятого» парня, поскольку он располагается слева от нее.
Расстановка «>><<>» будет неправильной, т.к. девушка на позиции 5 не найдет себе парня, т.к. парней недостаточно, чтобы все пары были сформированы.
Помогите Пете определить, является ли заданная расстановка правильной.
Входные данные. На вход программе подается единственная строке -расстановка танцующих, правильность которой необходимо проверить.
Выходные данные. В результате работы программа должна вывести на экран сообщение. Если расстановка правильная, то необходимо вывести «legal», если же нет, то «illegal» (без кавычек).
Ограничения. Расстановка состоит только из символов «<» или «>». Длина расстановки не превышает 10000 символов.
Замечание. Если программа на всех тестах выдает одинаковое сообщение (всегда «legal» или всегда «illegal»), то она получает 0 баллов.
Примеры:
| Вход | Выход |
| >><<>< | legal |
| ><<> | illegal |
| <<>> | illegal |
| >>><<< | legal |
| ><> | illegal |
Задача 2 «Конфеты»
Ввод данных — из файла input.txt Ограничение по памяти — 64 мегабайта
Вывод данных — в файл output.txt Ограничение времени — 1 секунда на тест
Однажды Петя, решая задачки, проголодался и решил пойти попить чай с конфетами. У него дома было много разных сортов конфет. Он выложил их всех в ряд и решил их есть не по порядку, а особым образом.
Сначала он находит в ряду две рядом лежащие конфеты одного сорта, съедает их, потом сдвигает все конфеты и опять ищет две рядом лежащие одного сорта, съедает их, и т.д.
У Пети много конфет, он хочет узнать сможет ли он съесть их все, таким способом.
Ввод
Сначала вводится целое число N (1 ≤ N ≤ 10000) – количество конфет.
Далее вводятся N целых чисел, каждое означает сорт конфеты. Числа больше 0 и не превышают 1000
Вывод
“Yes”, если Петя сможет съесть все конфеты или “No” в противном случае.
Пример
| Ввод | Вывод |
| 1 1 | YES |
| 1 1 1 | NO |
| 2 3 3 2 | YES |
Примечание:
2 3 3 2 -> 2 2 -> нет конфет
Сначала Петя съест две конфеты 3 сорта. Потом две конфеты 2 сорта. Значит, он может съесть все - выведем YES.