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

Контейнеры#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лёгкаяВойти и решать

Игра в пьяницу#38596

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

Для простоты будем считать, что все карты различны по номиналу, а также, что самая младшая карта побеждает самую старшую карту ("шестерка берет туза").

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

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

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

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

Примеры

№	Входные данные	Выходные данные
1	1 3 5 7 9 2 4 6 8 0	second 5

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

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

Практический тест#38589

У нас есть сетка с H строками и W столбцами. Квадрат в i-й строке и j-м столбце будет называться Square(i, j). Целые числа от 1 до H·W записаны по всей сетке, а целое число, записанное в Square(i, j), равно A_i,j.
Вы - волшебник (волшебница), и можете телепортировать фигуру, помещенную на Square(i, j) в Square(x, y), потратив \(|x-i|+|y-j|\) маджиков (магических монет).
Теперь вам нужно пройти Q практических тестов на свои способности как волшебника (волшебницы). I-е испытание будет проводиться следующим образом:
- первоначально фигура располагается в квадрате, где записано целое число L_i;
- пусть x будет целым числом, записанным в квадрате, занятом фигурой. Неоднократно переместите фигуру в квадрат, где написано целое число x+D, пока x не станет равен R_i. Тест заканчивается, когда x = R_i .
Гарантируется, что R_i- L_i делится на D.
Для каждого теста найдите сумму маджиков, израсходованных во время этого теста.

Входные данные
В первой строке заданы три целых числа: H, W и D (\(1\leq H,W \leq 300\), \(1 \leq D \leq H \cdot W\)).
В следующих H строках записано по W чисел A_i,j(\(1 \leq A_{i,j} \leq H \cdot W\), \(A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))\).
В следующей строке записано целое число Q (\(1 \leq Q \leq 10^5\)).
В последних Q строках записано по 2 целых числа: L_i и R_i (\(1 \leq L_i \leq R_i \leq H \cdot W\)), \((R_i-L_i)\) кратно D.

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

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 3 2 1 4 3 2 5 7 8 9 6 1 4 8	5	- 4 записано Square (1,2). - 6 записано в Square (3,3). - 8 записано in Square (3,1). Таким образом, сумма магических очков, израсходованных во время одного теста, составляет: \((\|3-1\|+\|3-2\|)+(\|3-3\|+\|1-3\|)=5\).
2	4 2 3 3 7 1 4 5 2 6 8 2 2 2 2 2	0 0	Обратите внимание, что может быть тест, в котором фигура вообще не перемещается, и может быть несколько идентичных тестов.
3	5 5 4 13 25 7 15 17 16 22 20 2 9 14 11 12 1 19 10 6 23 8 18 3 21 5 24 4 3 13 13 2 10 13 13	0 5 0

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

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

Перекраска клеток#38577

Дано клетчатое поле N x M, все клетки поля изначально белые. Автомат умеет:

закрасить клетку (i,j) в черный цвет.
для клетки (i,j) узнать её ближайших белых соседей по вертикали и горизонтали.
Дана последовательность команд для автомата. Требуется выполнить эти команды в указанной последовательности, и для каждой команды запроса ближайших белых соседей указать результат ее выполнения.

Входные данные
Сначала вводятся размеры поля N и M (1 ≤ N ≤ 20, 1 ≤ M ≤ 50000), затем количество команд K (1 ≤ K ≤ 10⁵), а затем сами команды. Команды записаны по одной в строке в следующем формате:

Color i j — окраска клетки (i,j) в черный цвет;
Neighbors i j — нахождение белых соседей для БЕЛОЙ клетки (i,j).

1 ≤ i ≤ N, 1 ≤ j ≤ M.

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

Примеры

№	Входные данные	Выходные данные
1	5 5 6 Color 4 2 Neighbors 4 3 Color 2 3 Color 3 3 Neighbors 4 3 Neighbors 5 1	4 4 1 4 4 3 3 5 3 4 4 1 4 4 1 3 5 3 2 5 2 4 1

Двумерные массивы Информатика Система непересекающихся множеств Список

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

Выбор цветов для букета#38384

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

Придя в цветочный магазин, Володя обнаружил, что букет можно составлять из цветов m различных видов, причём количество цветов каждого вида не ограничено. Володя знает, что от первого цветка i-го вида в букете его супруга становится счастливее на a_i, а от каждого следующего цветка
такого вида она становится счастливее на b_i. То есть, если в букете x_i > 0 цветов вида i, то от цветов этого вида жена Володи становится счастливее на a_i + (x_i − 1) · b_i.

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

Формат входных данных
В первой строке вводятся два целых числа n и m (1 ≤ n ≤ 10⁹ , 1 ≤ m ≤ 100 000) — требуемое
количество цветов в букете и количество доступных видов цветов.
Каждая из следующих m строк описывает i-й вид цветов и содержит два целых числа a_i и b_i (0 ≤ a_i , b_i ≤ 10⁹ ) — увеличение счастья от первого цветка i-го вида и увеличение счастья от каждого последующего цветка этого вида.

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

Примеры

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

Бинарный поиск в массиве Префиксные суммы(минимумы, ...)

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

Комфортабельные коровы#38142

Пастбище Фермера Юрика может рассматриваться как огромная 2D-решётка ячеек (шахматная доска). Изначально пастбище пустое.

Фермер Юрик добавит N (\(1<=N<=10^5\)) коров на пастбище одну за другой. i-ая корова займёт ячейку (x_i,y_i), которая отличается от ячеек, занятых всеми другими коровами (\(0<=x_i,y_i<=1000\)).

Корова называется "комфортабельной", если она имеет ровно трёх соседей по горизонтали и вертикали. Комфортабельные коровы дают меньше молока, поэтому Фермер Юрик хочет добавлять коров пока нет комфортабельных (включая ту которую он добавит). Заметим, что добавляемые коровы не обязательно должны иметь координаты x и y в интервале \(0…1000\).

Для каждого i в интервале \(1…N\), выведите минимальное количество коров, которое он должен добавить, чтобы не осталось комфортабельных коров, если считать, что на пастбище находятся только коровы \(1…i\).

Входные данные
Первая строка содержит целое число N. Каждая из следующих N строк содержит по 2 разделённых пробелом целых числа (x, y), указывающих координаты ячейки с коровой.

Выходные данные
Минимальное количество коров, которое Фермер Юрик должен добавить, для каждого i в интервале \(1…N\), на отдельной строке.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	9 0 1 1 0 1 1 1 2 2 1 2 2 3 1 3 2 4 1	0 0 0 1 0 0 1 2 4	Для i=4, Фермер Юрик должен добавить корову в позицию (2,1), чтобы сделать корову в позиции (1,1) некомфортабельной. Для i=9, лучшее что Фермер может сделать - добавить коров в позиции (2,0), (3,0), (2,−1), (2,3).

Очередь Разбор случаев

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

Достаточно зеленого#38139

Пастбище Фермера Джона может рассматриваться как NхN решётка (\(1<=N<=500\)) квадратных ячеек с травой (как большая шахматная доска). Из-за изменчивости почвы, трава в некоторых ячейках зеленее, чем в других. Каждая ячейка (i,j) описывается целым числом - уровнем зелёности G(i,j), в интервале \(1…200\).

Фермер Джон хочет сделать фотографию прямоугольной подрешётки своего пастбища. Он хочет, чтобы минимальная из величин G на его фотографии была ровна 100. Помогите ему посчитать, сколько таких различных фотографий он сможет сделать. Подрешётка может быть размером от всего пастбища и до одной ячейки. Всего существует \(N^2(N+1)^2/4\) различных подрешёток, для хранения такого числа используйте 64-битное целое (типа long long в C++).

Входные данные
Первая строка содержит N. Каждая из следующих N строк содержит N целых чисел и все вместе они описывают величины G(i,j) для пастбища NхN .

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

Заметим, что для ответа требуется использовать 64-битную целую переменную типа long long в C++.

Примеры

№	Входные данные	Выходные данные
1	3 57 120 87 200 100 150 2 141 135	8

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

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

Детская карточная игра#34979

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

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

Входные данные: Программа получает на вход две строки: первая строка содержит 5 чисел, разделенных пробелами — номера карт первого игрока, вторая – аналогично 5 карт второго игрока. Карты перечислены сверху вниз, то есть каждая строка начинается с той карты, которая будет открыта первой.
Выходные данные: Программа должна определить, кто выигрывает при данной раздаче, и вывести слово first или second, после чего вывести количество ходов, сделанных до выигрыша. Если на протяжении 10⁶ ходов игра не заканчивается, программа должна вывести слово botva.

Примеры

№	Входные данные	Выходные данные
1	1 3 5 7 9 2 4 6 8 0	second 5

Очередь

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

Исправляем 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средняяВойти и решать

*Сталкер#33469

В городе Н при невыясненных обстоятельствах территория одного из заводов превратилась в аномальную зону. Все подъезды к территории были перекрыты, а сама она получила название промзоны. В промзоне находятся N зданий, некоторые из них соединены дорогами. По любой дороге можно перемещаться в обоих направлениях.
Начинающий сталкер получил задание добраться до склада в промзоне. Он нашел в электронном архиве несколько карт территории промзоны. Так как карты составлялись разными людьми, то на каждой из них есть информация только о некоторых дорогах промзоны. Одна и та же дорога может присутствовать на нескольких картах.
В пути сталкер может загружать из архива на мобильный телефон по одной карте. При загрузке новой карты предыдущая в памяти телефона не сохраняется. Сталкер может перемещаться лишь по дорогам, отмеченным на карте, загруженной на данный момент. Каждая загрузка карты стоит 1 рубль. Для минимизации расходов сталкеру нужно выбрать такой маршрут, чтобы как можно меньшее число раз загружать карты. Сталкер может загружать одну и ту же карту несколько раз, при этом придется заплатить за каждую загрузку. Изначально в памяти мобильного телефона нет никакой карты.

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

Входные данные:
- в первой строке входных данных содержатся два натуральных числа N и K (\(2 <= N <= 2000\); \(1 <= K <= 2000\)) — количество зданий промзоны и количество карт соответственно. Вход в промзону находится в здании с номером 1, а склад — в здании с номером N.
- в последующих строках находится информация об имеющихся картах. Первая строка описания i-ой карты содержит число r_i — количество дорог, обозначенных на i-ой карте;
- затем идут r_i строк, содержащие по два натуральных числа a и b (\(1 <= a\), \(b <= N\); \(a ? b\)), означающих наличие на i-ой карте дороги, соединяющей здания a и b. Суммарное количество дорог, обозначенных на всех картах, не превышает 300 000 (\(r_1 + r_2 + … + r_K <= 300 000\)).

Выходные данные: выведите одно число — минимальную сумму расходов сталкера. В случае, если до склада добраться невозможно, выведите число –1.

Примеры

№	Входные данные	Выходные данные
1	12 4 4 1 6 2 4 7 9 10 12 3 1 4 7 11 3 6 3 2 5 4 11 8 9 5 3 10 10 7 7 2 12 3 5 12	3

0-1 BFS Дек

✓ 3✗ 951 300средняяВойти и решать

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

Кот Гусь и случайная матрица#33256

Кот Гусь подготовил для Ника Фьюри прямоугольную таблицу a размера \(n \cdot m\), содержащую числа от 0 до p−1. Ник Фьюри сразу понял, что каждое число в этой таблице выбрано случайно равновероятно от 0 до p−1, независимо от остальных.

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

Формально, вам необходимо найти такие \(1 <= i_1 <= i_2 <= n\), \(1 <= j_1 <= j_2 <= m\), что сумма a_x,y по всем \(i_1 <= x <= i_2\), \(j_1 <= y <= j_2\) делится на p, и среди таких имеет максимальную сумму.

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

В первой строке расположено три целых числа n, m, p (\(1 <= n·m, p <= 1 000 000\)) — размерности матрицы и число, на которое должна делится сумма подматрицы.

В следующих n строках расположено по m целых чисел, j-е число в i-й строке равно a_i,j (\(0 <= a_{i,j} <= p ? 1\)).

Гарантируется, что каждое число в a выбрано независимо случайно равновероятно от 0 до p−1.

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

Выведите одно целое число — максимальную сумму прямоугольной подматрицы, в которой сумма делится на p. Если таких нет, выведите 0.

Примеры

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

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

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

Городской парад#30782

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

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

Входные данные
Первая строка ввода содержит одно целое число N (\(1 <= N <= 100\)) – количество платформ.
Вторая строка содержит N различных целых чисел от 1 до N – номера платформ в порядке прибытия.

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

Примеры

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

Очередь

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

Морской бой - 3#30781

Всем известна увлекательная игра «Морской бой». Сейчас играть в Морской бой можно не только с соседом по парте, но и с компьютером. Игра c компьютером ведется на прямоугольном поле произвольных размеров N×M, где N - количество строк, M - количество столбцов. Приближается чемпионат мира по Морскому бою. Планируется вести его трансляцию в режиме реального времени: демонстрировать карту с кораблями и выводить статистику: количество целых, подбитых и уничтоженных кораблей, находящихся на поле. Требуется написать программу для подсчета статистики.

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

Входные данные
Первая строка содержит два целых числа N и M (\(1<= N,M <= 10^3\)), разделённых пробелами. Это размеры игрового поля. Далее идут N строк по M символов - описание игрового поля. Английская буква 'X' обозначает подбитую клетку корабля, 'S' - не подбитую клетку корабля, '-' – свободное водное пространство.

Выходные данные
В ответе выведите через пробел три числа:
- количество целых кораблей;
- количество подбитых кораблей;
- количество уничтоженных кораблей.

Примеры

№	Входные данные	Выходные данные
1	3 8 ---SSS-- XX--S-X- X-S---S-	2 1 1

Очередь

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