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

Censoring (Bronze)#90403

Фермер Джон купил подписку журнала Good Hooveskeeping для своих коров, теперь им есть что почитать. К несчастью, последний номер содержит довольно неподходящую статью, как приготовить совершенный бифштекс. ФД хочет чтобы его коровы не увидели эту статью.

ФД взял текст из журнала и создал строку S длиной не более чем 10^6 символов. Из неё он хочет удалить все вхождения подстроки T длиной <= 100 символов неподходящего содержания. Чтобы сделать это, ФД ищет первое вхождение T в S и удаляет его. Затем он повторяет процесс опять, снова удаляя первое вхождение T, продолжая так до тех пор, пока больше не станет вхождений T в S. Заметим, что удаление одного вхождения может создать другое вхождение, которое не существовало раньше.

Пожалуйста, помогите ФД определить конечное содержание строки S после завершения всех удалений.

Формат входных данных

Первая строка содержит S. Вторая строка будет содержать T. Длина T не более чем длина S, и все символы S и T - маленькие латинские буквы (a..z).

Формат выходных данных

Строка S после завершения всех удалений. Гарантируется, что S не станет пустой после завершения процесса всех удалений.

—Войти и решать

Хроноробот#84671

В 2147 году корпорация «ТемпоралТех» создала первого робота-разведчика для исследования опасных планет. Робот оснащён уникальной системой хронометок — устройством, позволяющим мгновенно вернуться в безопасную точку при обнаружении угрозы.

Робот перемещается по бесконечному полю и выполняет программу:

L — шаг влево (x уменьшается на 1)
R — шаг вправо (x увеличивается на 1)
U — шаг вверх (y увеличивается на 1)
D — шаг вниз (y уменьшается на 1)
( — установить хронометку (запомнить текущую позицию как безопасную)
) — экстренный возврат (переместиться к последней метке, метка исчезает)

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

Робот начинает разведку в точке (0, 0). По записи бортового журнала определи, в какой точке робот завершил миссию.

Пример

Журнал: RRR(RR)DD

Робот прошёл 3 клетки вправо, поставил метку на случай опасности, продолжил разведку ещё на 2 клетки вправо. Затем обнаружил угрозу и активировал возврат к метке. Оказавшись в безопасности, спустился на 2 клетки вниз.

Шаг  Команда  Позиция   Что произошло
─────────────────────────────────────────────
 0      —     (0, 0)    Старт миссии
 1      R     (1, 0)    Шаг вправо
 2      R     (2, 0)    Шаг вправо
 3      R     (3, 0)    Шаг вправо
 4      (     (3, 0)    Метка установлена
 5      R     (4, 0)    Шаг вправо
 6      R     (5, 0)    Шаг вправо
 7      )     (3, 0)    Возврат к метке!
 8      D     (3, -1)   Шаг вниз
 9      D     (3, -2)   Шаг вниз

Финальная позиция: 3 -2

Формат входных данных

Одна строка — запись бортового журнала.

Символы: L, R, U, D, (, )
Длина: от 1 до 10⁵ символов
Гарантируется корректность: каждому ) предшествует непогашенная (

Формат выходных данных

Два целых числа через пробел — координаты (x, y) финальной позиции робота.

Стек

✓ 2✗ 0—Войти и решать

Космический турнир#84529

В далёкой галактике проходит ежегодный Космический турнир по бластерболу. Правила подсчёта очков необычны:

Каждое попадание x приносит базовые очки
Капитан может активировать силовое поле, введя символ ( — пока оно активно, все очки удваиваются
Деактивация поля происходит по вводу символа ) — возврат к обычному режиму
Силовые поля могут быть вложенными — тогда множители перемножаются!

Запись матча — строка из символов x, ( и ). Подсчитай итоговый счёт команды.

Пример

Запись матча: xx(x(xx)x)x

Символ	Множитель	Очки	Пояснение
`x`	×1	+1	Обычный режим
`x`	×1	+1	Обычный режим
`(`	—	—	Поле активировано, ×2
`x`	×2	+2	Внутри поля
`(`	—	—	Второе поле, ×4
`x`	×4	+4	Двойная вложенность
`x`	×4	+4	Двойная вложенность
`)`	—	—	Внутреннее поле снято, ×2
`x`	×2	+2	Снова одинарное поле
`)`	—	—	Все поля сняты, ×1
`x`	×1	+1	Обычный режим

Итого: 1 + 1 + 2 + 4 + 4 + 2 + 1 = 15

Формат ввода

Одна строка, содержащая запись матча.

Символы: x (попадание), ( (активация поля), ) (деактивация)
Длина строки: 1 ≤ |s| ≤ 10⁵
Гарантируется корректность скобочной последовательности

Формат вывода

Одно целое число — итоговый счёт команды.

Стек

✓ 2✗ 2—Войти и решать

Магические руны#84528

Юный маг Алистер нашёл древний свиток с магическими рунами. Оказалось, что руны обладают странным свойством: когда две одинаковые руны оказываются рядом, они аннигилируют — исчезают со вспышкой света!

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

Формат входных данных

Вводится строка, содержащая символы английского алфавита

Формат выходных данных

Выведите результирующую строку

Пояснение к примеру

Свиток: abbaca

Руны bb аннигилируют → aaca
Руны aa аннигилируют → ca
Больше пар нет → ответ: ca

Стек

✓ 2✗ 6—Войти и решать

Сортировка вагонов#56036

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

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

Входные данные
Вводится число N — количество вагонов в поезде (1 ≤ N ≤ 100). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 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

Задачи на моделирование Стек

✓ 3✗ 0—Войти и решать

Конвейер#55459

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

накопитель перемещает первый контейнер из ленты в цех В;

накопитель перемещает первый контейнер из строки в склад (в складе каждый следующий контейнер помещается на предыдущий);

накопитель перемещает верхний контейнер из склада в цех В.

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

Входные данные
Первая строке содержит количество тестов N. Далее следует N строк, каждый из которых описывает отдельный тест и содержит целое число K (1≤ K ≤ 10000) — количество контейнеров в последовательности и K действительных чисел — степеней срочности контейнеров в порядке их поступления из цеха А (меньшим числам соответствует большая степень срочности).

Выходные данные
Каждая строка должна содержать ответ для одного теста. Необходимо вывести 1, если необходимое упорядочивание возможно, или 0 в противном случае.

Использование сортировки Стек

✓ 1✗ 0—Войти и решать

Сортировка вагонов#55398

Известно, в каком порядке изначально идут вагоны поезда. Требуется с помощью указанных операций сделать так, чтобы вагоны поезда шли по порядку (сначала первый, потом второй и т.д., считая от головы поезда, едущего по пути 2 в сторону от тупика).

Входные данные
Вводится число N — количество вагонов в поезде (1 ≤ N ≤ 2000). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от 1 до N, каждое из которых встречается ровно один раз.

Выходные данные
Если сделать так, чтобы вагоны шли в порядке от 1 до N, считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите действия, которые нужно проделать с поездом. Каждое действие описывается двумя числами: типом и количеством вагонов:

если нужно завезти с пути 1 в тупик K вагонов, должно быть выведено сначала число 1, а затем — число K (K≥1),
если нужно вывезти из тупика на путь 2 K вагонов, должно быть выведено сначала число 2, а затем — число K (K≥1).
Если возможно несколько последовательностей действий, приводящих к нужному результату, выведите любую из них.

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

Примеры

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

Задачи на моделирование Стек

✓ 1✗ 0—Войти и решать

Правильная скобочная последовательность#55367

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

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

По данной скобочной последовательности определите, является ли она правильной.

Входные данные
Программа получает на вход последовательность из скобок (открывающихся и закрывающихся скобок трех видов). Длина последовательности не превышает 255 символов. Последовательность не содержит пробелов (но после последнего символа могут идти пробелы и переходы на новую строку).

Выходные данные
Проверьте, является ли эта последовательность правильной. Выведите слово yes, если последовательность правильная и слово no в противном случае.

Стек

✓ 2✗ 0—Войти и решать

Скобки(2)#55113

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

Входные данные
В первой строке находится единственное число N. 1 <= N <= 14, N - чётное.

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

Перебор Стек

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

Скобки#55111

Дана последовательность из N круглых, квадратных и фигурных скобок. Выяснить, можно ли добавить в неё цифры и знаки арифметических действий так, чтобы получилось правильное арифметическое выражение.

Входные данные
В первой строке находится число скобок N, во второй - N символов из набора (, ), [, ], {, }. 1 <= N <= 100 000.

Выходные данные
Выводится слово "Yes", если получить правильное арифметическое выражение можно, или "No", если нельзя.

Стек

✓ 2✗ 0—Войти и решать

Ударим мостом по бездорожью#51095

Профиль Уральских гор задается ломаной (x₁, y₁), (x₂, y₂), …, (x_N, y_N), для координат вершин которой верны неравенства x₁ < x₂ < … < x_N. Начальные и конечные точки профиля расположены на уровне моря (y₁ = y_N = 0).

На горном профиле заданы две различные точки A и B, между которыми требуется проложить дорогу. Эта дорога будет проходить по склонам гор и проектируемому горизонтальному мосту, длина которого не должна превышать L. Оба конца моста находятся на горном профиле. Дорога заходит на мост с одного конца и выходит с другого. Мост не может содержать точек, расположенных строго под ломаной (строительство тоннелей не предполагается).
Возможные примеры расположения моста Невозможное расположение моста

Достоверно известно, что строительство такого моста в данной местности возможно, причем позволит сократить длину дороги из точки A в точку B. Требуется написать программу, которая определит такое расположение горизонтального моста, что длина дороги от точки A до точки B будет наименьшей.

Формат входных данных
Первая строка входных данных содержит два целых числа N и L — количество вершин ломаной (2 ≤ N ≤ 100 000) и максимальную длину моста (1 ≤ L ≤ 10⁶) соответственно. Вторая строка содержит координаты точки A, третья строка — координаты точки B. Точки A и B различны.

Последующие N строк содержат координаты вершин ломаной (x₁, y₁), (x₂, y₂), …, (x_N, y_N). Координаты вершин ломаной, а также точек A и B, задаются парой целых чисел, не превосходящих по абсолютному значению 106. Гарантируется, что x₁ < x₂ < … < x_N и y₁= y_N = 0, а также, что точки A и B принадлежат ломаной.

Формат выходных данных
В первой и второй строках выходных данных выведите координаты концов моста с точностью не менее 5 знаков после десятичной точки. В случае, когда решений несколько, выведите любое из них.

Динамическое программирование: один параметр Жадный алгоритм Стек

✓ 1✗ 13—Войти и решать

Стековое кодирование#50452

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

Изначально вам дан пустой стек и пустой массив. Кодом массива \(a\) назовем последовательность действий вида

\(\mathtt{push}(x)\) — положить число \(x\) на вершину стека;
\(\mathtt{pop}\) — снять число с вершины стека;
\(\mathtt{print}\) — выписать в конец массива все элементы стека по порядку от нижнего к верхнему,

приводящую к тому, что в изначально пустой массив оказываются выписаны все элементы \(a\) по порядку. При выполнении третьей операции стек не очищается.

Например, при выполнении последовательности действий \(\mathtt{push}(1)\), \(\mathtt{push}(2)\), \(\mathtt{print}\), \(\mathtt{print}\), \(\mathtt{pop}\) и \(\mathtt{print}\) в массив оказываются выписаны числа \([1, 2, 1, 2, 1]\), а на стеке остается лежать только число \(1\). То есть такая последовательность является кодом массива \([1, 2, 1, 2, 1]\) длины \(6\).

Вам дан массив \(a\) и \(q\) запросов: какой у отрезка массива \(a\) с \(l_i\)-го по \(r_i\)-й элемент включительно минимальный по количеству действий со стеком код?

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

Формат входных данных
В первой строке ввода даны четыре целых числа \(n\) и \(q\) — длина массива \(a\), про отрезки которого спрашивается в запросах, количество запросов, а также максимальный балл за тест и параметр \(\gamma\), указанный в системе оценивания, которые ваше решение может игнорировать \((1 \le n \le 2000\); \(1 \le q \le 10^4\)).

Во второй строке перечислены \(n\) целых чисел \(a_i\) — элементы массива \(a\) (\(1 \le a_i \le 10^9\)).

В \(i\)-й из следующих \(q\) строк даны два целых числа \(l_i\) и \(r_i\) — границы отрезка из \(i\)-го запроса (\(1 \le l_i \le r_i \le n\)).

Формат выходных данных
Для каждого запроса выведите в отдельной строке целое число \(k\) от \(1\) до \(n + 1\) — количество действий в вашем коде соответствующего отрезка массива, после чего в следующей строке выведите через пробел \(k\) целых чисел, описывающих эти действия в порядке их выполнения:

для действия \(\mathtt{push}(x)\) выведите число \(x\) от \(1\) до \(10^9\);
для действия \(\mathtt{pop}\) выведите число \(-1\);
для действия \(\mathtt{print}\) выведите число \(0\).

Если в результате выполнения выведенных действий происходит попытка снять число с вершины пустого стека или в конце не получается массив, равный заданному отрезку массива \(a\), ваше решение получает вердикт Wrong Answer. Также вы получите вердикт Wrong Answer, если в вашем коде будет больше \(n + 1\) действия.

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

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

Следующий больший элемент#45812

Следующий больший элемент некоторого элемента x в массиве - это первый больший элемент, который находится справа от x в том же массиве.

Вам даны два различных целочисленных массива nums1 и nums2 с индексами 0, где nums1 является подмножеством nums2.

Для каждого 0 <= i < nums1.length найдите индекс j такой, что nums1[i] == nums2[j] и определите следующий больший элемент nums2[j] в nums2. Если следующего большего элемента нет, то ответом на этот запрос будет -1.

Выведите n чисел таких, что каждое из них будет являться следующим большим элементом, как описано выше.

Входные данные
В первой строке записано натуральное число n - размер массива nums1. Вторая строка содержит n чисел - элементы массива nums1. В третьей строке записано натуральное число m - размер массива nums2. Четвертая строка содержит m чисел - элементы массива nums2.

Ограничения на входные данные

1 <= nums1.length <= nums2.length <= 50000
0 <= nums1[i], nums2[i] <= 10⁹
Все числа в массивах nums1 и nums2 уникальны.
Все числа массива nums1 содержатся в nums2.

a.length - размер массива a

Выходные данные
Выведите ответ на задачу.

Примеры

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

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

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

Длинный плакат#42975

Юный художник Вася нарисовал плакат с очень большим числом и решил повесить его на самую длинную стену школы. К сожалению, даже самая длинная стена оказалась недостаточно длинной, поэтому ему придется укорачивать плакат до нужной длины. Вася — максималист, поэтому он хочет, чтобы число, получившееся после всех правок, было как можно больше. Васе нужно вырезать из плаката любые K цифр, но он ни за что не согласится переставлять получившиеся кусочки местами, так как это нарушит цветовой баланс плаката. Помогите Васе переделать плакат.

Входные данные
В первой строке входных данных записано целое число N, записанное на изначальном длинном плакате. Гарантируется, что в N не менее двух и не более 200 000 цифр (10 ≤ N < 10^{200 000}).
Во второй строке содержится целое число K — количество цифр, которые необходимо вырезать из плаката. Гарантируется, что K не меньше одного и строго меньше количества цифр числа N (1 ≤ K, 10^K ≤ N).
Выходные данные
Выведите максимальное число, которое может получиться на плакате после его укорачивания

Примеры

№	Входные данные	Выходные данные
1	2023 1	223

Замечание
В примере из условия на плакате записано число 2023, из него нужно вырезать одну цифру.
Максимально число, которое можно при этом получить, равно 223.

Жадный алгоритм Стек

✓ 12✗ 751 200средняяВойти и решать

Нет времени рисовать#39574

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

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

.... -> BBB. -> BBLL -> BQQL
Ограниченная во времени, Беси может оставить некоторые последовательные отрезки не покрашенными. Сейчас она рассматривает Q кандидатов отрезков (1≤Q≤10⁵), каждый задаётся двумя целыми числами (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

Префиксные суммы(минимумы, ...)Стек

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

Стек с защитой от ошибок#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

Стек

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

Простой стек#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

Стек

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

Контейнеры#38599

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

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

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

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

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

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

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

Примеры

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

Стек

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

Постфиксная запись#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

Стек

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

Правильная скобочная последовательность#38597

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	()[]	yes

Стек

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