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

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

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

+-=#33254

Массив A содержит n целых чисел. Вывыдите знак >, если количество минимальных полжительных чисел больше, чем максимальных отрицательных. Выведите знак <, если количество минимальных положительных чисел меньше, чем максимальных отрицательных. При равенстве выведите знак =.
Если среди чисел нет положительных (отрицательных), то количество минимальных положительных (максимальных отрицательных) считать равным 0.

Входные данные
Первая строка входных данных содержит число n (0 <= n <= 10⁵). Вторая строка содержит n целых чисел a_i- элементы массива (-10⁹ <= a_i <= 10⁹).

Выходные данные
Выведите один знак (>, <, =) - ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	5 1 1 2 -2 -1	>
2	7 1 1 2 -1 -1 -2 -3	=

Одномерные массивы

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

Ослабление флота#33252

Кэрол Дэнверс, известная как Капитан Марвел противодействует флоту Скруллов. Каждый из

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

Кэрол считает, что настолько сильна, что может не только вывести из строя флот, но и немного

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

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

мощность которого является медианой мощностей оставшихся кораблей.

Медиану ряда чисел Кэрол вычисляет следующим образом:

• Если количество чисел в ряду нечетно, то медиана — число, стоящее посередине упорядоченного по возрастанию данного ряда.

• Если количество чисел в ряду чётно, то медианой ряда является:

– Меньшее из двух стоящих посередине чисел упорядоченного по возрастанию данного ряда, если два средних различны.

– Любое из двух стоящих посередине чисел упорядоченного по возрастанию данного ряда,

если два средних равны.

Помогите Капитану Марвел посчитать порядок, в котором нужно атаковать корабли.

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

В первой строке дано одно натуральное число n — число кораблей во флоте Скруллов (1 <= n <= 10⁵).

Во второй строке содержатся n натуральных чисел ai — мощность i-го корабля (1 <= a_i <=10⁹).

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

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

Ввод	Вывод
3 8 3 19	8 3 19
4 4 2 2 1	2 2 1 4

"Два указателя"

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

Один конь#33251

На шахматной доске NxN в клетке (x1, y1) стоит голодный шахматный конь. Он хочет попасть в клетку (x2, y2), где растет вкусная шахматная трава. Какое наименьшее количество ходов он должен для этого сделать?

Формат входных данных
На вход программы поступает пять чисел: N, x₁, y₁, x₂, y₂(\(5 <= N <= 20\), \(1 <= x_1,\ y_1,\ x_2,\ y_2 <= N\)). Левая верхняя клетка доски имеет координаты (1, 1), правая нижняя - (N, N).

Формат входных данных
Выведите единственное число K - наименьшее необходимое число ходов коня.

Обход в ширину

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

Пара с минимальной суммой#33250

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

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

В первой строке входных данных задаётся количество чисел N (\(1 < N <= 10000\)).
В каждой из последующих N строк записано одно натуральное число, не превышающее 10000.

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

Примеры

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

ЕГЭ - вычислительные задачи

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

Префикс-функция#33249

Дана непустая строка S, длина которой N не превышает \(10^6\). Будем считать, что элементы строки нумеруются от 1 до N.

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

Значением префикс-функции \(\pi[i]\) будем считать длину этой подстроки.

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

Требуется для всех i от 1 до N вычислить \(\pi[i]\).

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

Одна строка длины N, \(0 < N <= 10^6\), состоящая из маленьких латинских букв.

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

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

Примеры

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

Z-функция. Префикс-функция

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

Вывод четных#33233

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

Входные данные
Сначала задано число N — количество элементов в массиве (1<=N<=100). Далее через пробел записаны N чисел — элементы массива. Массив состоит из целых чисел, по модулю не превышающих 100.

Выходные данные
Необходимо вывести все четные элементы массива.

Примеры

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

Одномерные массивы

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

Нечетные индексы#33232

Дан массив, состоящий из N целых чисел. Нумерация элементов начинается с 0. Напишите программу, которая выведет элементы массива с нечетными индексами (1, 3, 5...).

Входные данные
Сначала задано число N — количество элементов в массиве (1<=N<=100). Далее через пробел записано N чисел — элементы массива. Массив состоит из целых чисел, по модулю не превышающих 100.

Выходные данные
Необходимо вывести все элементы массива с нечётными индексами.

Примеры

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

Одномерные массивы

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

Суммарная длина дорог#33227

Найдите суммарную длину всех дорог в городе Новые Васюки. Схема дорог задана в виде весовой матрицы графа. На некоторых дорогах введено одностороннее движение. Если длины дорог из пункта А в пункт Б разные, это означает, что есть две разные дороги.

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

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

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

Программа должна вывести одно число – суммарную длину дорог. Дороги с двусторонним движением нужно считать только один раз.

Ввод	Вывод
5 0 2 3 4 0 2 0 5 0 7 3 6 0 8 0 0 0 0 0 0 0 7 0 9 0	44

Алгоритмы на графах

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

Количество дорог#33226

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

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

В первой строке вводится количество перекрёстков в Новых Васюках N ( 1 ≤ N ≤ 1000 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы матрицы смежности графа, который описывает схему дорог.

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

Программа должна вывести одно число – количество дорог в Новых Васюках. Дороги с двусторонним движением нужно считать только один раз.

Ввод	Вывод
5 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 0 0 0 0 1 0 1 0	7

Алгоритмы на графах

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

Использование массивов#33225

Для каких из следующих данных НЕ подходит массив:
1. хранение оценок ученика за двенадцать промежуточных экзаменов;
2. хранение имени, номера социального обеспечения, возраста и дохода одного человека;
3. хранение температуры, принятой за каждый час в течение дня;
4. хранение общего объема продаж в магазине, за каждый из двенадцати месяцев.

Одномерные массивы

300лёгкаяВойти и решать

Vector: Начало#33200

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

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

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

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

Примеры

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

Массивы

✓ 1 201✗ 4 664200лёгкаяВойти и решать

Банкет#33147

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

Входные данные: В первой строке входных данных содержатся два числа: N и M (1 <= N,M <= 100), где N – количество ОВП, а M – количество пар ОВП, которые не могут сидеть за одним столом. В следующих M строках записано по 2 числа – пары ОВП, которые не могут сидеть за одним столом.

Выходные данные: Если способ рассадить ОВП существует, то выведите YES в первой строке и номера ОВП, которых необходимо посадить за первый стол, во второй строке. В противном случае в первой и единственной строке выведите NO.

Примеры

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

Обход в глубину

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

Баобаб#33146

Дан неориентированный невзвешенный граф. Необходимо определить, является ли он деревом.

Формат входных данных
В первой строке содержится одно натуральное число N (N ≤ 100) - количество вершин в графе. Далее в N строках по N чисел - матрица смежности графа: в i-ой строке на j-ом месте стоит 1, если вершины i и j соединены ребром, и 0, если ребра между ними нет. На главной диагонали матрицы стоят нули. Матрица симметрична относительно главной диагонали.

Формат выходных данных
Вывести "YES", если граф является деревом, и "NO" иначе.

Обход в глубину

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

Два измерения#33144

Ученые планируют провести важный эксперимент с использованием исследовательского модуля

на планете X-2019. В процессе эксперимента будет проведено два измерения: основное и контрольное.

Каждое измерение занимает ровно один час и должно начинаться спустя целое число часов после

начала работы исследовательского модуля.

Данные эксперимента планируется немедленно передать на орбитальную станцию. Канал связи

с орбитальной станцией будет установлен с l-го по r-й час от начала работы исследовательского модуля, включительно. Кроме того, согласно плану эксперимента между измерениями планета

должна совершить целое число оборотов вокруг своей оси. Планета X-2019 осуществляет оборот

вокруг своей оси за a часов.

Таким образом, если измерения осуществляются на i-м и j-м часу, то должно выполняться неравенство l <= i < j <= r, а величина (j − i) должна быть кратна a. Теперь учёным необходимо понять,

сколько существует различных способов провести измерения.

Требуется написать программу, которая по заданным границам времени измерений l и r и периоду обращения планеты вокруг своей оси a определяет количество возможных способов провести

измерения: количество пар целых чисел i и j, таких что l <= i < j <= r, и величина (j − i) кратна a.

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

Входные данные содержат три целых числа, по одному на строке: l, r и a (1 <= l < r <= 10⁹,1 <= a <= 10⁹).

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

Выведите одно целое число: количество способов провести измерения.

Ввод	Вывод
1 5 2	4
4 9 6	0

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

В первом примере можно провести измерения в следующие пары часов: (1, 3), (1, 5), (2, 4), (3, 5).

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

измерения.

Вывод формулы

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

Ход конем - 2#33143

Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить только так, как показано на рисунке:

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

Входные данные
Во входной строке находятся два натуральных числа N и M (\(1 <= N,\ M <= 15\)).

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

Примеры

№	Входные данные	Выходные данные
1	4 4	2
2	7 15	13309

Динамическое программирование: два параметра

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

Ход конем_1#33142

Дана прямоугольная доска N × M (N строк и M столбцов). В левом верхнем углу находится шахматный конь, которого необходимо переместить в правый нижний угол доски. При этом конь может ходить ТОЛЬКО на две клетки вниз и на одну клетку вправо, либо на две клетки вправо и на одну клетку вниз (смотри рисунок).

Входные данные
Во входной строке находятся два натуральных числа N и M (\(1 <= N,\ M <= 50\)).

Примеры

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

Динамическое программирование: два параметра

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

Двудольный граф#33138

Граф называется двудольным, если его вершины можно раскрасить в два цвета так, что нет ребер, соединяющих вершины одинакового цвета (то есть каждое ребро идет из вершины 1-го цвета в вершину 2-го).

Дан граф. Требуется проверить, является ли он двудольным, и если да, то раскрасить его вершины.

Входные данные
В первой строке задано сначала число N - количество вершин графа (не превышает 100). Далее идет матрица смежности - матрица размером NxN из 0 и 1 (0 обозначает отсутствие ребра, 1 - наличие). Граф неориентированный, без петель.

Выходные данные
В первую строку выведите одно из сообщений YES или NO (в зависимости от того, является ли граф двудольным или нет). В случае ответа YES, во второй строке выведите N чисел - цвета, в которые нужно раскрасить вершины: для первого цвета используйте значение 1, для второго цвета - значение 2. Первая вершина должна иметь цвет 1.

Примеры

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

Применение обхода в глубину

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

Долой списывание!#33137

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

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

Входные данные: В первой строке находятся два числа N и M - количество студентов и количество пар студентов, обменивающихся записками (1<=N<=100, 0<=M<=(N(N−1))/2. Далее в M строках расположены описания пар студентов: два числа, соответствующие номерам студентов, обменивающихся записками (нумерация студентов идёт с 1). Каждая пара студентов перечислена не более одного раза.

Выходные данные: Необходимо вывести ответ на задачу профессора Флойда. Если возможно разделить студентов на две группы - выведите YES; иначе выведите NO.

Примеры

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

Применение обхода в глубину

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

Поиск компонент сильной связности#33136

Вам задан ориентированный граф с N вершинами и M ребрами (1<=N<=20000, 1<=M<=200000). Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию.

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

Граф задан во входном файле следующим образом: первая строка содержит числа N и M. Каждая из следующих M строк содержит описание ребра — два целых числа из диапазона от 1 до N — номера начала и конца ребра.

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

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

Ввод	Вывод
10 19 1 4 7 8 5 10 8 9 9 6 2 6 6 2 3 8 9 2 7 2 9 7 4 5 3 6 7 3 6 7 10 8 10 1 2 9 2 7	2 1 2 2 1 1 2 2 2 2 1

Компоненты сильной связности

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