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

Haybale Stacking#89826

Беси согласилась помочь ФД уложить пакеты с сеном. Она начинает с N (1 <= N <= 1,000,000, N нечетное) пустых стеков, пронумерованных от 1 до N. Затем ФД дает ей последовательность из K инструкций (1 <= K <= 25,000), каждая вида A B, означающая, что Беси должна добавить по одному пакету с сеном в каждый из стеков в диапазоне от A до B. Например, инструкция 10 13 означает, что Беси должна положить по пакету сеном в стеки 10, 11, 12, 13.
После того как вся работа закончена, ФД хочет узнать медианную высоту всех N своих стеков - то есть высоту среднего стека, если все стеки упорядочить по высоте. По условию N нечетно, поэтому этот стек уникален. Пожалуйста, помогите Беси ответить на этот вопрос.
PROBLEM NAME: stacking
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N K.
* Строки 2..1+K: Каждая строка содержит одну инструкцию ФД в виде двух целых (разделенных пробелом) чисел A B (1 <= A <= B <= N).

Формат выходных данных
* Строка 1: Медианная высота после того как Беси выполнит все инструкции

Примечание
После того, как Беси закончит, стеки будут иметь высоты 0,1,2,3,3,1,0. Если их упорядочить, получим: 0,0,1,1,2,3,3. Средний элемент равен 1.

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

Above the Median#89800

Problem 1: Above the Median [Brian Dean]
Фермер Джон выстроил N (1 <= N <= 100,000) своих коров, чтобы померять их высоты. Корова i имеет высоту H_i (1 <= H_i <= 1,000,000,000) нанометров. ФД производит очень точные измерения! ФД хочет сфотографировать некоторую непрерывную последовательность своих коров, и послать эту фотографию на соревнование.
Допускается к соревнованию только фотография группы коров, у которой медианная высота не менее чем заданная величина X (1 <= X <= 1,000,000,000).
В этой задаче мы определяем медианой массива A[0..K] значение A[ceiling(K/2)] после того, как A отсортировали. Здесь ceiling(K/2) – это округление K/2 до ближайшего целого. Например, медиана от {7, 3, 2, 6} есть 6, а медиана от {5,4,8} есть 5.
Помогите ФД посчитать количество различных непрерывных последовательностей коров, фотографии которых будут допущены к соревнованию.
PROBLEM NAME: median
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа: N и X.
* Строки 2..N+1: Строка i+1 содержит одно целое число H_i.
Формат выходных данных
* Строка 1: Количество подпоследовательностей коров ФД, у которых медиана не менее X. Заметим, что это число может не поместиться в 32-битное целое.
Примечание
Всего существует 10 непрерывных последовательностей. Однако только 7 из них имеют медиану не менее 6: {10}, {6}, {10, 5}, {5, 6}, {6, 2}, {10, 5, 6}, {10, 5, 6, 2}.

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

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

Хроноробот#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—Войти и решать

САМЫЙ ЯРКИЙ УЧАСТОК ФОТО#81890

У вас есть фотография, и вы хотите вырезать из неё квадратный кусочек k×k с максимальной суммарной яркостью пикселей. Программа получает на вход размеры фотографии n и m, затем n строк по m чисел - яркость пикселей, затем размер вырезаемого квадрата k. Программа должна вывести максимальную сумму яркости, которую можно получить, вырезав квадрат k×k из фотографии. Подсказка: нужно проверить все возможные позиции для квадрата k×k!

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

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

66149#66149

В маленьком городе N, где нет ни интернета, ни телефонов, живут лучшие друзья Коля, Маша, Саша и Наташа. В очередной зимний день им очень хотелось провести время, играя в какую-нибудь игру, но такую, чтобы игра была не очень быстрой. Потому Маша предложила ребятам сыграть в своего рода модифицированную карточную версию игры «Пьяница» под названием «Круговерть_2».
Правила игры оказались следующими:

·игрокам заранее раздают поровну перетасованную колоду из52 карт (четыре масти: червы, бубны, трефы, пики, в каждой из которых 13 карт), таким образом у каждого игрока оказывается своя колода карт, стоящая в виде стопки, расположенной рубашкой вниз;
·каждый ход игроки выкладывают на стол по одной картесверху своей колоды на стол, по порядку слева-направо (первый игрок, второй игрок, третий и четвёртый), далее происходит определение победителей:
- если карты одной масти, то побеждает тот, у кого картабыла наибольшего значения (порядок карт в порядке их значения по возрастанию: туз, 2-10, валет, дама, король); туз - самая слабая карта;
- если карты разных мастей, то побеждает тот, у когомасть выше по значению (порядок мастей по возрастанию: червы, бубны, трефы, пики);
- если карт высшей масти несколько, то рассматриваетсяопределение наибольшего значения среди этих карт (например, выложили 10 червы, 8 бубны, 7 трефы, 8 трефы, то карты разных мастей, потому выбирается наибольшая масть – в данном случае трефы, таких карт две, среди них самая наибольшая 8 трефы, потому побеждает игрок 4);
·победитель забирает четыре карты в свою колоду по порядку,кладя сперва карту первого игрока под низ колоды, затем второго, третьего, четвёртого;
·побеждает тот игрок, который заберёт все картыпротивников.

Коля очень любит программирование, потому он решил заранее рассчитать, сколько им понадобится ходов, чтобы был определён победитель (у кого будут все 52 карты), потому ему требуется помочь написать программу, которая по входным данным игры определит через сколько ходов будет определён победитель игры. Если же за 1000 ходов победитель так и не определится, то вывести, сколько карт оказалось у первого игрока, у второго, третьего, четвёртого.
Входные данные:
на первых 13 строках подаются карты первого игрока (в порядке их нахождения в стопке карт),
далее на 13 строках подаются карты второго игрока (в порядке их нахождения в стопке карт),
далее на 13 строках подаются карты третьего игрока (в порядке их нахождения в стопке карт),
далее на 13 строках подаются карты четвёртого игрока (в порядке их нахождения в стопке карт).
Все карты подаются в формате <масть>, <значение>.
Масти обозначаются следующим образом (одна латинская буква в нижнем регистре):

c – червы;
b – бубны;
t – трефы;
p – пики.

Значения карт с картинками обозначаются следующим образом (одна латинская буква в нижнем регистре):

t – туз;
v – валет;
d – дама;
k – король.

Например:

(t,10) – десятка треф;
(c, t) – туз червей.

Выходные данные:
Если за 1000 ходов (включительно) кто-то победит, то вывести количество ходов и номер победившего игрока (например, 340 2, что означает, что за 340 ходов победил игрок №2).
Если за 1000 ходов (включительно) минимум у двух игроков останутся карты (никто не победит), то вывести количество карт по завершении 1000-го хода у первого игрока, у второго, у третьего, у четвёртого на одной строке через пробел (например, 48 3 1 0).
Примечание
•карты перечисляются в вводе так, как они лежат сверху-вниз,если сперва дали туз, затем 10, то на дне колоды лежит 10, а на верху туз, который будет вытащен первым.

Задачи на моделирование Очередь

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

66148#66148

В маленьком городе N, где нет ни интернета, ни телефонов, живут лучшие друзья Коля и Маша. В очередной зимний день им очень хотелось провести время, играя в какую-нибудь игру, но такую, чтобы игра была не очень быстрой. Потому Маша предложила Коле сыграть в своего рода модифицированную карточную версию игры «Пьяница» под названием «Круговерть».
Правила игры оказались следующими:
·игрокам заранее раздают поровну перетасованную колоду из52 карт (четыре масти: червы, бубны, трефы, пики, в каждой из которых 13 карт), таким образом у каждого игрока оказывается своя колода карт, стоящая в виде стопки, расположенной рубашкой вниз;

каждый ход игроки выкладывают на стол по одной картесверху своей колоды на стол, далее происходит определение, кто заберёт карты:

- если карты одной масти, то забирает карты тот, у когокарта была наибольшего значения (порядок карт в порядке их значения по возрастанию: туз, 2-10, валет, дама, король); туз - самая слабая карта;
- если карты разных мастей, то забирает карты тот, у когомасть выше по значению (порядок мастей по возрастанию: пики, червы, бубны, трефы);

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

Коля очень любит программирование, потому он решил заранее рассчитать, сколько им понадобится ходов, чтобы был определён победитель (у кого не будет карт), потому ему требуется помочь написать программу, которая по входным данным игры определит через сколько ходов будет определён победитель игры. Если же за 1000 ходов победитель так и не определится, то вывести, сколько карт оказалось у первого игрока и сколько у второго.
Входные данные:
на первых 26 строках подаются карты первого игрока (в порядке их нахождения в стопке карт),
далее на 26 строках подаются карты второго игрока (в порядке их нахождения в стопке карт).
Все карты подаются в формате <масть>, <значение>.
Масти обозначаются следующим образом (одна латинская буква в нижнем регистре):

c – червы;
b – бубны;
t – трефы;
p – пики.

Значения карт с картинками обозначаются следующим образом (одна латинская буква в нижнем регистре):

t – туз;
v – валет;
d – дама;
k – король.

Например:

(t,10) – десятка треф;
(c, t) – туз червей.

Выходные данные:
Если за 1000 ходов (включительно) кто-то победит, то вывести количество ходов и номер победившего игрока (например, 340 2, что означает, что за 340 ходов победил игрок №2).
Если за 1000 ходов (включительно) у всех останутся карты (никто не победит), то вывести количество карт по завершении 1000-го хода у первого игрока и у второго на одной строке через пробел (например, 50 2).
Примечание
•карты перечисляются в вводе так, как они лежат сверху-вниз,если сперва дали туз, затем 10, то на дне колоды лежит 10, а на верху туз, который будет вытащен первым.

Задачи на моделирование Очередь

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

65873#65873

Галактическая станция «Вавилон» имеет N (0 < N <= 10) ангаров для космических кораблей.
Цикл предполетной подготовки длится M (0 < M <= 10) суток. Цикл начинается в тот же момент, как корабль залетает в ангар. До окончания цикла корабль не может покинуть ангар и соответственно начать новый рейс.
Сутки на станции составляют 24 часа. Календарь на станции составляет 365 дней, которые не делятся на месяцы.
Вам попали в руки фрагменты станционного журнала (0 < K <= 1000 строк). В нем фиксируются даты и время прибытия кораблей в зону станции, а также заявки на рейсы со станции. Гарантируется, что все страницы относятся к одному году.
Если корабль подлетает к станции, а все ангары заняты, то ему отказывают в обслуживании. Если вылет со станции назначен на тот же час, что и прилет нового корабля, будем считать, что сначала ангар освобождается, а потом новый корабль размещается в пустом ангаре (начало цикла будет считаться с момента прилета).
Если приходит запрос на рейс со станции, то в рейс уходит тот корабль, который готов к вылету. Если таких кораблей несколько, то выбирается тот, который дольше находится на станции. Если готовых к рейсу кораблей нет, то рейс задерживают и ждут, когда появится корабль, который пройдет цикл предполетной подготовки. Если до конца периода кораблей для выполнения рейса не найдется, то заявка считается НЕ задержанной, а отклоненной.
По данным журнала определите скольким кораблям было отказано и сколько рейсов было отклонено в рассматриваемый период.

Входные данные:
В первой строке через пробел три числа N M K.
Дальше K строк в формате
День Час Признак
Где День – это номер дня от начала года; Час – час события; Признак это 1, если корабль прилетает, -1, если это запрос на вылет.
Выходные данные:
Два целых числа, каждое на новой строке:
– количество отказов в обслуживании;
– количество отклоненных заявок.

Примечание
В журнале 9 записей.
1) 1 9 1
2) 8 12 -1
3) 6 15 -1
4) 6 12 -1
5) 2 18 1
6) 5 6 1
7) 6 12 1
8) 7 12 -1
9) 2 21 1
Корабли, прибывшие 1-го в 9:00 и 2-го в 18:00, были поставлены в два ангара, имеющиеся на станции (1-ая и 5-ая строки журнала).
6-го числа в 12:00 1-ый ангар покинул корабль по заявке из 4-ой строки журнала. В тот же момент его место занял корабль с 7-ой строки.
На момент прилета кораблей из 6-ой и 9-ой строк оба ангара были заняты. Эти корабли получили отказ.
Выполнение заявок с 3-ей и 8-ой строк журнала было задержано, так как не было готовых к вылету кораблей.
Заявка со 2-ой строки была отклонена, так как в ангарах и на подлете в рассматриваемый интервал времени кораблей не было.

Жадный алгоритм Очередь

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

Летовецкая дуэль#60946

В деревне Летовецк, где живут мудрые старцы и их ученики, существует древняя игра, которая называется "Летовецкая дуэль". В этой игре два игрока сражаются друг с другом, используя стопку из 10 уникальных карточек, каждая из которых имеет значение от 0 до 9. Карточки раздаются поровну: каждому игроку достаётся по 5 карточек.

Правила игры просты:

Игроки одновременно открывают верхнюю карточку своей стопки.
Тот, чья крточка старше, забирает обе вскрытые карточки и кладёт их под низ своей стопки. При этом сначала кладётся карточка первого игрока, затем карточка второго.
Игра продолжается до тех пор, пока у одного из игроков не закончатся карточки. Этот игрок проигрывает.
Особое правило: карточка со значением 0 побеждает карточку со значением 9, даже если 9 обычно старше 0.

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

Формат входных данных
Программа получает на вход две строки: первая строка содержит 5 чисел, разделенных пробелами — номера карточек первого игрока, вторая – аналогично 5 карточек второго игрока. Карточки перечислены сверху вниз, то есть каждая строка начинается с той карточки, которая будет открыта первой.

Формат выходных данных
Программа должна определить, кто выигрывает при данной раздаче, и вывести слово first или second, после чего вывести количество ходов, сделанных до выигрыша. Если на протяжении 10⁶ ходов игра не заканчивается, программа должна вывести слово botva.

Очередь

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

Гармония#60824

Совсем недавно Васе на день рождения подарили строку, состоящую только из символов «0» и «1». Обрадованный этим подарком, он тут же начал эту строку изучать — искать в ней гармоничные части. Для начала Васю интересует только количество различных непустых гармоничных подстрок. А поскольку подарок оказался слишком большим, мальчик решил обратиться за помощью к вам. Помогите Васе!
В понимании Васи, строка является гармоничной, если и символов 0, и символов 1 в ней чётное количество.
Подстрокой строки s называется строка, полученная из s выкидыванием нескольких символов с начала и с конца (возможно, нуля или всех). Так, строка «12» является подстрокой строки «123», а строка «13» — нет. Подстроки считаются одинаковыми, если у них совпадает количество удалённых символов с начала и с конца.

Формат входных данных
В первой строке дано одно число n — длина подарка (1 ≤ n ≤ 2 · 10⁵ ). Во второй строке дана строка s длины n — Васин подарок. Гарантируется, что s состоит только из нулей и единиц.
Формат выходных данных
Выведите единственное число — количество различных гармоничных подстрок в s.
Обратите внимание, что значение ответа в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64- битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

Замечание
В первом примере из условия подходят следующие подстроки (выделены жирным): 001100, 001100, 001100, 001100, 001100, 001100, 001100.

Префиксные суммы(минимумы, ...)реализация

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

4#58516

Динамическое программирование: один параметр Префиксные суммы(минимумы, ...)

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

Длина последовательности#57757

Рассмотрим отрезок целых неотрицательных чисел от \(l\) до \(r\). Запишем их подряд в десятичной системе счисления, получив строку \(a\). Например, если \(l=3\), \(r=10\), то \(a=345678910\).

Найдите такой отрезок подряд идущих неотрицательных чисел \([l,r]\) (\(0 \le l \le r \le 10^{18}\)), что записанная для него строка \(a\) имеет длину ровно \(S\), а количество чисел на отрезке \([l,r]\) максимально.

Формат входных данных
Первая строка содержит одно целое число \(S\) (\(1 \le S \le 10^{18}\)).

Формат выходных данных
В первой строке выведите длину отрезка \([l,r]\). Если решения не существует, выведите одно целое число \(-1\).

Если решение существует, во второй строке выведите искомые границы отрезка \(l\) и \(r\).

Если существуют несколько решений, выведите любое из них.

"Два указателя"Префиксные суммы(минимумы, ...)

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

Подводная лодка#56309

Подводная лодка легла на грунт на мелководье. Для её обнаружения используются данные спутника, который с высокой точностью измеряет отклонение высоты поверхности воды от среднего уровня моря. Снимок, получаемый со спутника, представляет собой массив из \(h\) строк по \(w\) элементов в каждой строке.

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

<<корпус>> — полоса из элементов с координатами от \((x_1, y_1)\) до \((x_2, y_1)\), где \(x_1 < x_2\);
<<рубка>> — полоса из элементов с координатами от \((x_3, y_1)\) до \((x_3, y_2)\), где \(x_1 \leq x_3 < x_2\); \(y_1 \leq y_2\);
<<хвост>> — полоса из элементов с координатами от \((x_4, y_3)\) до \((x_4, y_4)\), где \(x_3 < x_4 \leq x_2\); \(y_3 \leq y_1 \leq y_4\).

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

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

Входные данные
Для сжатия передаваемых со спутника данных каждый элемент снимка кодируется строчной буквой английского алфавита. Первая строка входных данных содержит число \(k\) — количество использованных для кодирования букв (\(k \le 26\)). Вторая строка входных данных содержит \(k\) целых чисел \(c_i\) — значения отклонений соответствующих каждому кодовому символу по порядку букв в английском алфавите от 1 до \(k\)-й.

Третья строка входных данных содержит числа \(h\) и \(w\) — размеры снимка. Последующие \(h\) строк содержат по \(w\) символов — кодовые значения элементов снимка.

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

Примеры

№	Входные данные	Выходные данные	Изображение
1	2 -10 1 6 11 aaaaaaaaaaa aaabaaaaaaa aaabaaaabaa abbbbbbbbba aaaaaaaabaa aaaaaaaaaaa	13	........... ...b....... ...b....b.. .bbbbbbbbb. ........b.. ...........
2	3 -4 -3 4 5 5 bbabc ccaac accba baccb baaaa	16	..... .c... .cc.. ..c.. .....
3	3 -2 4 0 5 5 abccb cccac cbcba cccbb accba	24	.b... .c... .b.b. cccbb ...b.
4	4 -1 -5 -3 0 5 5 bbabc ccaac acdba baccb baaaa	-2	..... ..aa. ..... ..... .....

Пояснение

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

Ниже приведены несколько множеств элементов снимка, которые не являются потенциальными изображениями подводной лодки:

Префиксные суммы(минимумы, ...)реализация

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

Сортировка вагонов#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—Войти и решать

Минимум на отрезке#55364

Рассмотрим последовательность целых чисел длины N. По ней с шагом 1 двигается “окно” длины K, то есть сначала в “окне” видно первые K чисел, на следующем шаге в “окне” уже будут находиться K чисел, начиная со второго, и так далее до конца последовательности. Требуется для каждого положения “окна” определить минимум в нём.

Входные данные
В первой строке входных данных содержатся два числа N и K (1 ≤ N ≤ 150000, 1 ≤ K ≤ 10000, K ≤ N) – длины последовательности и “окна”, соответственно. На следующей строке находятся N чисел – сама последовательность.

Выходные данные
Выходые данные должны содержать N − K + 1 строк – минимумы для каждого положения “окна”.

Дек Дерево отрезков, RSQ, RMQ

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

Скобки(2)#55113

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

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

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

Перебор Стек

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