Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Исправляем XML#34978

Формат 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>

Стек

✓ 26✗ 1331 100средняяВойти и решать

Доктор Хаус#34977

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

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

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	7 +1 +2 +3 ?2 - - ?1	5 3 2 1

Стек

✓ 149✗ 439700средняяВойти и решать

Разворот последовательности#34970

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

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

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

Примеры

№	Входные данные	Выходные данные
1	1 2 3 4 5 0	5 4 3 2 1

Стек

✓ 1 126✗ 1 683500лёгкаяВойти и решать

Реализация структуры стек с защитой от ошибок#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

Стек

✓ 23✗ 87700средняяВойти и решать

Реализация структуры стек - 1#34968

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

Стек

✓ 26✗ 59700средняяВойти и решать

Сортировка вагонов#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

Стек

✓ 1 106✗ 1 645600лёгкаяВойти и решать

Modern Art 2#27219

Picowso решила переключиться на 1-мерный стиль.

Теперь её картины могут описываться 1-мерным массивом цветов длины NN (1≤N≤100,000). А вот стиль у неё остался прежний: Он начинает на пустом отрезке и рисует отрезками. Она использует каждый из цветов 1…N ровно один раз, хотя некоторые из цветов могут быть полностью скрыты к концу рисования.

Moonet, соперник Picowso, придумал, как копировать картины Picowso. Он рисует множество не соединяющихся интервалов и т.д. Moonet может рисовать не более одного интервала каждого цвета во время всего процесса. Вычислите количество таких раундов, которые требуются Moonet, чтобы скопировать 1-мерную картину Picowso.

ФОРМАТ ВВОДА:

Первая строка ввода содержит N, и следующие N строк содержат целое число в интервале 0…N, указывающее цвет каждой ячейки на 1-мерном холсте (0 для пустой ячейки).

ФОРМАТ ВЫВОДА:

Выведите минимальное количество раундов, которое требуется для копирования заданного рисунка или -1, если невозможно повторить этот рисунок стилем, аутеничным стилю Picowso (то есть, её нельзя нарисовать слоями последовательностей интервалов, по одному каждого цвета).

Ввод	Вывод
7 0 1 4 5 1 3 3	2

Примечание
В данном примере интервал цвета 1 должен быть закрашен в более раннем раунде, чем интервалы цветов 4 и 5, поэтому необходимо как минимум два раунда.

Конструктив Линейные структуры Стек

✓ 2✗ 81 000средняяВойти и решать

Вычисление арифметических выражений#21882

Постфиксная запись представляет собой такую запись алгебраического выражения, в которой сначала записываются операнды, а затем – знак операции. Например, для выражения a + b * c постфиксная запись будет a b c * +.

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

Входные данные
На вход подается символьная строка. Знак / в записи означает целочисленное деление.

Выходные данные
Выведите на экран результат выражения.

Примеры

№	Входные данные	Выходные данные
1	5 3 + 7 4 - *	24

Разбор выражений Стек

✓ 863✗ 986500лёгкаяВойти и решать

Инфиксная в постфиксную#21881

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

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

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

Примеры

№	Входные данные	Выходные данные
1	(5+3)(7+24)	5 3 + 7 2 4 * + *

Стек

✓ 243✗ 1 206900средняяВойти и решать

Математическое выражение#21878

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

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

Выходные данные
Если скобки расставлены верно, то вывести на экран слово Yes, в противном случае - No и количество неправильно расставленных скобок (скобка считается неправильно расставленной, если у нее нет пары).

Примеры

№	Входные данные	Выходные данные
1	7-((X*((X+Y)/(J-3))+Y)/(4-2.5))	Yes
2	(a-c/(d)	No. Incorrect brackets = 1

реализация Стек

✓ 595✗ 1 569600лёгкаяВойти и решать

Скобки#21877

Напишите программу, которая проверяет правильность расстановки скобок в арифметическом выражении. Используются скобки трёх типов: ( ), [ ] и { }.

Входные данные
На вход подается строка.

Выходные данные
Выведите на экран Yes, если в строке правильного расставлены скобки. В противном случае, выведите No.

Примеры

№	Входные данные	Выходные данные
1	(5+7)[5+{(4+3)[9-6]+7}-8]	Yes
2	[(2+3)	No

Задача на реализацию Стек

✓ 1 270✗ 2 745500лёгкаяВойти и решать