Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 34968. Реализация структуры стек - 1
Темы: Стек   

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

push n
Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.

pop
Удалить из стека последний элемент. Программа должна вывести его значение.

back
Программа должна вывести значение последнего элемента, не удаляя его из стека.

size
Программа должна вывести количество элементов в стеке.

clear
Программа должна очистить стек и вывести ok.

exit
Программа должна вывести bye и завершить работу.

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

Команды управления стеком вводятся в описанном ранее формате по 1 на строке.

Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в стеке в любой момент не превосходит 100, все команды pop и back корректны, то есть при их исполнении в стеке содержится хотя бы один элемент.

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

Требуется вывести протокол работы со стеком, по 1 сообщению в строке

Примеры
входные данные

push 3
push 14
size
clear
push 1
back
push 2
back
pop
size
pop
size
exit

выходные данные
ok
ok
2
ok
ok
1
ok
2
2
1
1
0
bye

ID 34969. Реализация структуры стек с защитой от ошибок
Темы: Стек   

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

push n
Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.

pop
Удалить из стека последний элемент. Программа должна вывести его значение.

back
Программа должна вывести значение последнего элемента, не удаляя его из стека.

size
Программа должна вывести количество элементов в стеке.

clear
Программа должна очистить стек и вывести ok.

exit
Программа должна вывести bye и завершить работу.

Перед исполнением операций back и pop программа должна проверять, содержится ли в стеке хотя бы один элемент. Если во входных данных встречается операция back или pop, и при этом стек пуст, то программа должна вместо числового значения вывести строку error.


Входные данные: Вводятся команды управления стеком, по одной на строке

Выходные данные: Программа должна вывести протокол работы стека, по одному сообщению на строке

Примеры
входные данные
size
push 1
size
push 2
size
push 3
size
exit
выходные данные
0
ok
1
ok
2
ok
3
bye

ID 34977. Доктор Хаус
Темы: Стек   

Каждый день к Грегори Хаусу приходит много больных, и у каждого измеряется уровень гемоглобина в крови. Данные по всем пациентам заносятся в базу данных.

Но волчанка попадается один раз на миллион, а работать с остальными неинтересно. Чтобы Хаус не выгонял больных, Кадди иногда запрашивает статистику по последним больным: ей хочется знать сумму их уровня гемоглобина.

Также Хаус — мизантроп: он смотрит уровень гемоглобина больного, который поступил к нему позже всех, и, видя, что это точно не волчанка, выписывает его из больницы и удаляет информацию о нем из базы.

Автоматизацию процесса Хаус поручил Чейзу. Но Чейз почему-то не справился с этой задачей и попросил вас ему помочь.

Входные данные: Первой строкой входного файла задано число ( 1<= <= 100000 )  — число обращений к базе данных. Запросы к базе выглядят следующим образом: x ( 1 <=x <= 10 )  — добавить пациента с уровнем гемоглобина в базу, - — удалить последнего пациента из базы, ( 1 <= k <= 100000 )  — вывести суммарный гемоглобин последних пациентов. Гарантируется, что не превосходит число элементов в базе. Также гарантируется, что запросов на удаление к пустой базе не поступает. Перед началом работы база данных пуста.

Выходные данные: Для каждого запроса " - " вывести уровень гемоглобина в крови пациента, а для каждого запроса " ? " — суммарный гемоглобин у последних поступивших пациентов. Ответы выводите в порядке поступления запросов.


Примеры
Входные данные Выходные данные
1 7
+1
+2
+3
?2
-
-
?1
5
3
2
1

ID 34978. Исправляем XML
Темы: Стек   

Формат XML является распространенным способом обмена данными между различными программами. Недавно программист Иванов написал небольшую программу, которая сохраняет некоторую важную информацию в виде XML-строки.

XML-строка состоит из открывающих и закрывающих тегов.

Открывающий тег начинается с открывающей угловой скобки (<), за ней следует имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка (>).
Примеры открывающих тегов: <a>, <dog>.

Закрывающий тег начинается с открывающей угловой скобки, за ней следует прямой слеш (/), затем имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка.
Примеры закрывающихся тегов: </a>, </dog>.

XML-строка называется корректной, если она может быть получена по следующим правилам:
  • Пустая строка является корректной XML-строкой.
  • A и B — корректные XML-строки, то строка AB, получающаяся приписыванием строки B в конец строки A, также является корректной XML-строкой.
  • Если A — корректная XML-строка, то строка <X>A</X>, получающаяся приписыванием в начало A открывающегося тега, а в конец — закрывающегося с таким же именем, также является корректной XML-строкой. Здесь X — любая непустая строка из строчных букв латинского алфавита.
Например, представленные ниже строки:
<a></a>
<a><ab></ab><c></c></a>
<a></a><a></a><a></a>
являются корректными XML-строками, а такие строки как:
<a></b>
<a><b>
<a><b></a></b>
не являются корректными XML-строками.

Иванов отправил файл с сохраненной XML-строкой по электронной почте своему коллеге Петрову. Однако, к сожалению, файл повредился в процессе пересылки: ровно один символ в строке заменился на некоторый другой символ.
Требуется написать программу, которая по строке, которую получил Петров, восстановит исходную XML-строку, которую отправлял Иванов.

Входные данные: Входной файл содержит одну строку, которая заменой ровно одного символа может быть превращена в корректную XML-строку. Длина строки лежит в пределах от 7 до 1000, включительно. Строка содержит только строчные буквы латинского алфавита и символы «<» (ASCII код 60), «>»(ASCII код 62) и «/»(ASCII код 47).
Строка во входном файле заканчивается переводом строки.

Выходные данные: Выходной файл должен содержать корректную XML-строку, которая может быть получена из строки во входном файле заменой ровно одного символа на другой. Если вариантов ответа несколько, можно вывести любой.
 
Примеры
Входные данные Выходные данные
1 <a></b> <a></a>
2 <a><aa> <a></a>
3 <a><>a> <a></a>
4 <a/</a> <a></a>

ID 34970. Разворот последовательности
Темы: Стек   

Вводится последовательность целых чисел, оканчивающаяся нулем. Число 0 в последовательность не входит.
Выведите элементы последовательности в обратном порядке. Для хранения данных используйте стек.

Входные данные 
Вводится последовательность целых чисел, по модулю не превосходящих 10000. Ввод заканчивается, когда будет введено число 0. Всего чисел не более 100 (не считая нуля).

Выходные данные 
Выведите элементы этой последовательности в обратном порядке, через пробел.

 

Примеры
Входные данные Выходные данные
1 1 2 3 4 5 0 5 4 3 2 1

ID 21881. Инфиксная в постфиксную
Темы: Стек   

Напишите программу, которая переводит арифметическое выражение, записанное в инфиксной формы в постфиксную. 

Входные данные
На вход подается строка, представляющая из себя инфексную форму записи выражения (в строке отсутствуют пробелы).

Выходные данные
Выведите на экран постфиксную форму данного выражения, отделяя каждый операнд и операцию друг от друга одним пробелом.
 

Примеры
Входные данные Выходные данные
1 (5+3)*(7+2*4) 5 3 + 7 2 4 * + *

ID 33292. Сортировка вагонов
Темы: Стек   

Требуется определить, возможна ли сортировка последовательности чисел с помощью стека.

К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании можно даже завезти в тупик сразу весь поезд). После этого часть вагонов вывезти в сторону пути 2. Потом можно завезти в тупик еще несколько вагонов, и снова часть вагонов транспортировать в сторону пути 2. И так далее, чтобы каждый вагон лишь один раз заехал с пути 1 в тупик, а затем один раз выехал из тупика на путь 2. Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.

Известно в каком порядке изначально идут вагоны поезда. Требуется, с помощью указанных операций, сделать так, чтобы вагоны поезда шли по порядку (сначала первый, потом второй и т.д., считая от головы поезда, едущего по пути 2 в сторону от тупика). Напишите программу, определяющую, можно ли это сделать.
 
Входные данные
Вводится число N — количество вагонов в поезде (\(1<=N<=2000\)). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от 1 до N, каждое из которых встречается ровно один раз.
 
Выходные данные
Можно ли сделать так, чтобы вагоны шли в порядке от 1 до N, считая от головы поезда, когда поезд поедет по пути 2 из тупика? Если можно, выведите сообщение YES. Если нельзя, то выведите NO.
 
 
Примеры
Входные данные Выходные данные Примечание
1 3
3 2 1
YES Надо весь поезд завезти в тупик, а затем целиком вывезти его на 2-й путь
2
4
4 1 3 2
YES
Сначала надо в тупик завезти два вагона, один из которых оставит в тупике, а второй — вывезти на 2-й путь, после чего завезти в тупик еще два вагона и вывезти 3 вагона, стоящие в тупике, на 2-й путь
3 3
2 3 1
NO  

ID 38597. Правильная скобочная последовательность
Темы: Стек   

Рассмотрим последовательность, состоящую из круглых, квадратных и фигурных скобок. Программа дожна определить, является ли данная скобочная последовательность правильной.

Пустая последовательность явлется правильной. Если A – правильная, то последовательности (A), [A], {A} – правильные. Если A и B – правильные последовательности, то последовательность AB – правильная.

Входные данные
В единственной строке записана скобочная последовательность, содержащая не более 100000 скобок.

Выходные данные
Если данная последовательность правильная, то программа должна вывести строку yes, иначе строку no.

Примеры
Входные данные Выходные данные
1 ()[] yes

ID 38598. Постфиксная запись
Темы: Стек   

В постфиксной записи (или обратной польской записи) операция записывается после двух операндов. Например, сумма двух чисел A и B записывается как A B +. Запись B C + D * обозначает привычное нам (B + C) * D, а запись A B C + D * + означает A + (B + C) * D. Достоинство постфиксной записи в том, что она не требует скобок и дополнительных соглашений о приоритете операторов для своего чтения.

Входные данные
В единственной строке записано выражение в постфиксной записи, содержащее цифры и операции +, -, *. Числа и операции разделяются пробелами. В конце строки может быть произвольное количество пробелов.

Выходные данные
Необходимо вывести значение записанного выражения.

Примеры
Входные данные Выходные данные
1 8 9 + 1 7 - * -102

ID 38599. Контейнеры
Темы: Стек   

На складе хранятся контейнеры с товарами N различных видов. Все контейнеры составлены в N стопок. В каждой стопке могут находиться контейнеры с товарами любых видов (стопка может быть изначально пустой).

Автопогрузчик может взять верхний контейнер из любой стопки и поставить его сверху в любую стопку. Необходимо расставить все контейнеры с товаром первого вида в первую стопку, второго вида – во вторую стопку и т.д.

Программа должна вывести последовательность действий автопогрузчика или сообщение о том, что задача решения не имеет.

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

В первой строке входных данных записано одно натуральное число N, не превосходящее 500. В следующих N строках описаны стопки контейнеров: сначала записано число ki – количество контейнеров в стопке, а затем ki чисел – виды товара в контейнерах в данной стопке, снизу вверх. В каждой стопке вначале не более 500 контейнеров (в процессе переноса контейнеров это ограничение может быть нарушено).

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

Программа должна вывести описание действий автопогрузчика: для каждого действия напечатать два числа – из какой стопки брать контейнер и в какую стопку класть. (Обратите внимание, что минимизировать количество операций автопогрузчика не требуется.) Если задача не имеет решения, необходимо вывести одно число 0. Если контейнеры изначально правильно размещены по стопкам, то  выводить ничего не нужно.

Примеры
Входные данные Выходные данные Пояснение
1 3
4 1 2 3 2
0
0
1 2
1 3
1 2
Изначально в первой стопке лежат четыре контейнера – снизу контейнер с товаром первого вида, над ним – с товаром второго вида, над ним третьего, и сверху еще один контейнер с товаром второго вида. Вторая и третья стопки – пусты.

ID 38600. Простой стек
Темы: Стек   

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

push n
Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.
pop
Удалить из стека последний элемент. Программа должна вывести его значение.
back
Программа должна вывести значение последнего элемента, не удаляя его из стека.
size
Программа должна вывести количество элементов в стеке.
clear
Программа должна очистить стек и вывести ok.
exit
Программа должна вывести bye и завершить работу.
Входные данные
Команды управления стеком вводятся в описанном ранее формате по 1 на строке.

Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в стеке в любой момент не превосходит 100, все команды pop и back корректны, то есть при их исполнении в стеке содержится хотя бы один элемент.

Выходные данные
Требуется вывести протокол работы со стеком, по 1 сообщению в строке

Примеры
Входные данные Выходные данные
1 push 3
push 14
size
clear
push 1
back
push 2
back
pop
size
pop
size
exit
ok
ok
2
ok
ok
1
ok
2
2
1
1
0
bye

ID 38601. Стек с защитой от ошибок
Темы: Стек   

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

push n
Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.
pop
Удалить из стека последний элемент. Программа должна вывести его значение.
back
Программа должна вывести значение последнего элемента, не удаляя его из стека.
size
Программа должна вывести количество элементов в стеке.
clear
Программа должна очистить стек и вывести ok.
exit
Программа должна вывести bye и завершить работу.
Перед исполнением операций back и pop программа должна проверять, содержится ли в стеке хотя бы один элемент. Если во входных данных встречается операция back или pop, и при этом стек пуст, то программа должна вместо числового значения вывести строку error.
Входные данные
Вводятся команды управления стеком, по одной на строке

Выходные данные
Программа должна вывести протокол работы стека, по одному сообщению на строке
 

Примеры
Входные данные Выходные данные
1 size
push 1
size
push 2
size
push 3
size
exit
0
ok
1
ok
2
ok
3
bye

ID 39574. Нет времени рисовать
Темы: Стек    Префиксные суммы(минимумы, ...)   

Беси недавно получила набор красок, и она хочет разрисовать длинную изгородь с одной стороны её пастбища. Изгородь состоит из N последовательных 1-метровых сегментов (1≤N≤105). У Беси есть краски 26 различных цветов, которые она пометила буквами от 'A' до Z' в порядке возрастания темноты ('A' - самый светлый цвет, 'Z' - самый тёмный). Поэтому она может описывать раскраску изгороди как строку из N символов (где каждый символ один из - от 'A' до Z').
Изначально все сегменты изгороди не раскрашены. Беси может раскрасить любой непрерывный диапазон сегментов одним цветом за одно прикосновение кисти, также она никогда не красит более светлым поверх более темного (она может красить более темным поверх более светлого).

Например, изначально не покрашенный отрезок длины 4 она может покрасить так:

.... -> BBB. -> BBLL -> BQQL
Ограниченная во времени, Беси может оставить некоторые последовательные отрезки не покрашенными. Сейчас она рассматривает Q кандидатов отрезков (1≤Q≤105), каждый задаётся двумя целыми числами (a,b) (1≤a≤b≤N), указывающих индексы конечных точек отрезка, которые должны остаться не раскрашенными.

Для каждого кандидата укажите минимальное количество прикосновений, которое требуется, чтобы раскрасить все сегменты вне этого диапазона с желаемым цветом, оставляя сегменты внутри диапазона не раскрашенными. Заметим, что Беси в реальности ничего не раскрашивает, поэтому ответы для каждого диапазона-кандидата независимы.

Входные данные
Первая строка содержит N и Q.
Следующая строка содержит N, представляющих желаемый цвет каждого сегмента изгороди.

Каждая из следующих Q строк содержит два разделённых пробелом целых числа a и b представляющих диапазон сегментов, которые возможно останутся не раскрашенными.

Выходные данные
Для каждого из Q кандидатов выведите ответ на новой строке.

Примеры
Входные данные Выходные данные Пояснение
1
8 2
ABBAABCB
3 6
1 4
4
3
В этом примере, исключение диапазона соответствует желаемому образцу В этом примере исключение диапазона BAAB требует четыре прикосновения для раскраски, а исключение диапазона ABBA - только три.

.... -> AA.. -> ABBB -> ABCB