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

Городской парад#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

Очередь

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

Морской бой - 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

Очередь

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

Поддержка максимума#30755

Дана последовательность чисел. Для каждого числа вывести текущий максимум на момент его ввода.

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

Задано сначала число N (количество чисел в последовательности, 1<=N<=100000), а затем N чисел.

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

Выведите текущие максимумы.

Примеры

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

Куча

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

Пирамида (максимум)#30723

Напишите программу, которая будет обрабатывать последовательность запросов таких видов:

CLEAR — сделать пирамиду пустой (если в пирамиде уже были какие-то элементы, удалить все). Действие происходит только с данными в памяти, на экран ничего не выводится.

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

EXTRACT — вынуть из пирамиды максимальное значение. Следует и изменить данные в памяти, и вывести на экран или найденное максимальное значение, или, если пирамида была пустой, слово "CANNOT" (большими буквами).

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

Во входных данных записано произвольную последовательность запросов CLEAR, ADD и EXTRACT — каждый в отдельной строке, согласно вышеописанному формату. Данные заканчиваются строкой "END!"

Суммарное количество всех запросов не превышает 200000.

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

Для каждого запроса типа EXTRACT выведите на стандартный выход (экран) его результат (в отдельной строке).

Ввод	Вывод
ADD 192168812 ADD 125 ADD 321 EXTRACT EXTRACT CLEAR ADD 7 ADD 555 EXTRACT EXTRACT EXTRACT END!	192168812 321 555 7 CANNOT

Куча

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

Банды Фомина №2#30699

Банда Фомина состоит из n групп, в каждой из которых a_i человек. Планируется провести q рейдов. В i-ом рейде будет участвовать ровно один разбойник из каждой группы, номер которой лежит в отрезке \([l_i, r_i]\).

Мелехов тоскует, поэтому для каждого рейда он решил посчитать количество возможных отрядов по модулю \(10^9 + 7\). Однако Григорий постоянно находится в раздумьях о смысле жизни и поиске правды, поэтому он не может сконцентрироваться на расчетах и просит вас помочь.

Входные данные
В первой строке дано число n (\(1 <= n <= 10^5\)) – количество групп в банде Фомина.
Во второй строке дано n натуральных чисел a_i (\(1 <= a_i <= 10^6\)) – количество человек в i-ой группе.
В третьей строке дано число q – количество рейдов.
Далее дано q строк, в каждой из которых дано два числа – l_i и r_i (\(1 <= l_i <= r_i <= n\)) – номера групп, участвующих в i-ом рейде.

Выходные данные
Выведите q чисел, каждое в отдельной строке – ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	6 1 3 7 1 4 100 3 1 3 3 4 2 6	21 7 8400

Быстрое возведение в степень Малая теорема Ферма Остатки Префиксные суммы(минимумы, ...)

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

Банды Фомина#30691

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

В первой строке дано число n (\(1 <= n <= 10^5\)) – количество групп в банде Фомина.

Во второй строке дано n натуральных чисел a_i (\(1 <= a_i <= 2\)) – количество человек в i-ой группе.

В третьей строке дано число q – количество рейдов.

Далее дано q строк, в каждой из которых дано два числа – l_i и r_i (\(1 <= l_i <= r_i <= n\)) – номера групп, участвующих в i-ом рейде.

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

Выведите q чисел, каждое в отдельной строке – ответ на задачу.

Примеры

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

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

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

Сумма на отрезке#30659

Дан неизменяемый массив длины n и q запросов типа “вычислить сумму подотрезка массива с l по r”. Выведите ответ на каждый запрос.

Входные данные
В первой строке дано число n – размер массива (\(1 <= n <= 10^5\)). Во второй строке дано n чисел – элементы массива. Числа по модулю не превосходят \(10^9\). В третьей строке дано число q – кол-во запросов (\(1 <= q <= 10^5\)). Далее дано q строк, в каждой из которых дано 2 числа: l и r (\(1 <= l <= r <= n\)).

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

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

Примеры

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

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

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

Cart Sorting#29658

У Акакия есть колода, состоящая из n карт. На каждой карте написано ровно одно целое число от 1 до 100 000. Возможно, что на некоторых картах написаны одинаковые числа.

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

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

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

В первой строке следует целое положительное число n (1 ≤ n ≤ 100 000) — количество карт в колоде.

Во второй строке следует последовательность из n целых положительных чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ 100 000), где a_i равно числу, написанному на i-й сверху карте из колоды.

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

Выведите суммарное количество раз, которое Акакий посмотрит верхнюю карту из колоды.

Ввод	Вывод
4 6 3 1 2	7
1 1000	1
7 3 3 3 3 3 3 3	7

Примечание

В первом примере Акакий посмотрит сначала карту с числом 6, положит ее вниз колоды, затем карту с числом 3, также положит ее вниз колоды, и затем карту с числом 1. Он отложит карту с числом 1, так как на ней написан минимальное число из оставшихся в колоде. После этого карты в колоде будут лежать в порядке [2, 6, 3] сверху вниз. После этого Акакий посмотрит верхнюю карту с числом 2 и отложит её. После этого карты в колоде будут лежать в порядке [6, 3] сверху вниз. Затем Акакий посмотрит карту с числом 6, положит ее вниз колоды, а затем карту с числом 3, которую отложит. После этого в колоде останется одна карта с числом 6, которую Акакий посмотрит и отложит. Таким образом, Акакий посмотрит 7 карт.

(с) Курбатов Е., 2018

Декартово дерево

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

Рубка деревьев#29655

Чубатый учит Григория Мелехова выполнять баклановский удар шашкой. В качестве целей, они используют n деревьев, стоящих в ряд и пронумерованных от 1 до n. Чубатый, оценил прочность всех деревьев натуральными числами, и записал их. За каждое дерево, которое Мелехов смог разрубить, он получает количество очков равное числу, записанному на дереве, а если не смог - то теряет столько же.

Чубатый просит Григория выполнить удары на деревьях с l по r, в порядке возрастания их номеров. Мелехов недавно ушиб плечо, потому он может успешно срубить дерево через раз, т. е. если он срубил дерево с номером i, то он не сможет срубить дерево с номером i + 1, но сможет срубить дерево с номером i + 2 и т. д.

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

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

В первое строке содержатся 2 числа n и m (\(1 <= n, m <= 100000\))

Во второй строке содержатся n чисел - прочность всех деревьев, где на позиции i написана прочность дерева i.

В следующих m строках содержатся пары чисел l и r (\(1 <= l <= r <= n\)), означающие какой отрезок деревьев попросил срубить Чубатый.

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

На каждый запрос выведите сколько очков в эту попытку заработал Григорий.

Примеры

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

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

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

Очередная задача про запросы в массиве#29654

Вам дается массив a размера n и q запросов к нему. Есть запросы двух типов:

1 l_i r_i — осуществить циклический сдвиг отрезка [l_i, r_i] вправо. То есть, для каждого такого x, что l_i ≤ x < r_i, a_x_+ 1 становится равным прежнему значению a_x, а a_li становится равным прежнему значению a_ri;
2 l_i r_i — перевернуть отрезок [l_i, r_i].

Необходимо вывести массив после обработки всех запросов.

Входные данные
В первой строке записаны два целых числа n и q (1 ≤ n, q ≤ 2·10⁵).
Во второй строке записаны n целых чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹).
Дальше идут q строк. В i-й из них записаны три целых числа t_i, l_i, r_i, где t_i — тип i-го запроса, [l_i, r_i] — отрезок, на котором запрос выполняется (1 ≤ t_i ≤ 2, 1 ≤ l_i ≤ r_i ≤ n).

Выходные данные
Выведите m чисел, i-е из которых равно числу на позиции b_i после обработки всех запросов.

Ввод	Вывод
6 3 1 2 3 4 5 6 2 1 3 2 3 6 1 1 6	1 3 2 6 5 4

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

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

Поиск числа на отрезке#29653

Дан массив a длины n (\(1 <= n <= 10^6\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 500\)) запросов вида +, l, r, k (\(1 <= l <= r <= n\), \(-10^9 <= k <= 10^9\)) и запросов вида ?, l, r, k (\(1 <= l <= r <= n\), \(-10^9 <= k <= 10^9\)).

В первом случае нужно добавить к числам на отрезке от l до r включительно, число k.
Во втором случае нужно вывести 1, если на отрезке от l до r включительно, есть число k, иначе вывести 0.

Элементы нумеруются с 1 до n.

Гарантируется, что после любого запроса любой элемент массива a лежит в диапазоне от \(-10^9\) до \(10^9\) включительно.

Примеры

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

sqrt декомпозиция

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

Умножение на отрезке#29652

Дан массив a длины n (\(1 <= n <= 2 \cdot 10^6\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 500\)) запросов вида *, l, r, k (\(1 <= l <= r <= n\), \(0 <= k <10\)) и запросов вида ?, i (\(1 <= i <= n\)).

В первом случае нужно умножить числа на отрезке от l до r включительно на k.

Во втором случае нужно вывести число, стоящее на позиции i.

Элементы нумеруются с 1 до n.

Примеры

№	Входные данные	Выходные данные
1	5 1 1 1 1 1 3 ? 3 * 2 3 9 ? 3	1 9

sqrt декомпозиция

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

Максимум на матрице#29651

Дана матрица a размером \(n \cdot n\) (\(1 <= n <= 1000\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 1000\)) запросов вида x₁, y₁, x₂, y₂ (\(1 <= x_1 <= n\), \(1 <= y_1 <= n\), \(x_1 <= x_2 <= n\), \(y_1 <= y_2 <= n\)).

На каждый запрос нужно вывести максимальный элемент в подматрице с координатами краёв x₁, y₁иx₂, y₂.

Примеры

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

sqrt декомпозиция

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

Сумма на отрезке - 2#29650

Дан массив a длины n (\(1 <= n <= 2 \cdot 10^6\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 500\)) запросов вида t, l, r (\(0 <= t <= 1\), \(1 <= l <= r <= n\)).

Если \(t = 0\), то на запрос нужно вывести сумму чисел на отрезке от l до r включительно. Если \(t = 1\), то элементу с номером l присваивается значение r. Элементы нумеруются с 1 до n.

Примеры

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

sqrt декомпозиция

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

Сумма на отрезке - 1#29649

Дан массив a длины n (\(1 <= n <= 2 \cdot 10^6\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 500\)) запросов вида l, r (\(1 <= l <= r <= n\)).

На каждый запрос нужно вывести сумму чисел на отрезке от l до r включительно. Элементы нумеруются с 1 до n.

Примеры

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

sqrt декомпозиция

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

Тихий дон №2#29640

Аксинья любит Григория, но она замужем за Степаном. Со своим мужем она несчастна, поэтому время, которое она проводит с ним можно характеризовать отрицательным показателем счастья Аксиньи (\(a_i < 0\)), а то время, которое она проводит с Григорием, - положительным показателем счастья (\(a_i > 0\)). Известно, что Аксинья проводит один день либо с мужем, либо с Григорием.

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

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

В первой строке подается 3 числа: N – кол-во дней, L и C (\(1 <= L, C <= N <= 1 000 000\)).

Во второй строке содержится N чисел a_i (\(1 <= |a_i| <= 1 000 000 000\)).

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

Требуется вывести ответ на задачу.

Примеры

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

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

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

Тихий Дон №3#29638

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

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

Григорий дает Наталье массив A, состоящий из n целых неотрицательных чисел. Затем он просит ее сделать q однотипных операций, заключающихся в следующем: "Даны числа l, r и k. Далее для каждого индекса i от l до r происходит подстановка числа k вместо числа A_i и считается побитовое исключающее “или” всех чисел на отрезке \([l;r]\), после чего на iое место опять возвращается число A_i".
Таким образом, происходит \(r – l + 1\) независимых подстановок, не меняющих массив, и соответственно \(r – l + 1\) результатов побитового исключающего “или”. Наталье необходимо сообщить Григорию побитовое исключающее “или” всех результатов подстановок (для лучшего понимания ознакомьтесь с примерами).

Помогите Наталье Коршуновой справиться с этой задачей! Тогда Григорий точно вернется к ней!

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

В первой строке дано целое число n (\(1 <= n <= 10^5\)) – количество элементов массива.

Во второй строке содержится n целых неотрицательных чисел, не превышающих по значению \(10^8\).

В третьей строке дано целое число q (\(1 <= q <= 10^5\)) – количество запросов.

Далее содержится q строк, в каждой из которых содержится 3 целых числа: l, r, k (\(1 <= l <= r <= n\), \(0 <= k <= 10^8\)).

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

Вам необходимо вывести q ответов на каждый запрос в одной строке через пробел.

Примеры

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

Пояснение

Первый запрос:

1) 7 ⊕ 2 ⊕ 3 = 6

2) 1 ⊕ 7 ⊕ 3 = 5

3) 1 ⊕ 2 ⊕ 7 = 4

6 ⊕ 5 ⊕ 4 = 7

Ответ: 7.

Второй запрос:

1) 10 ⊕ 5 = 15

2) 4 ⊕ 10 = 14

15 ⊕ 14 = 1

Ответ: 1.

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

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

Два одинаковых массива#28345

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

Входные данные
В первой строке записано натуральные числа N и M– количество элементов первого и второго массива соответственно, (1 <= N, M <= 10⁸). В следующих двух строках записаны элементы массива A и B. Во второй строке - элементы массива A, в третьей - элементы массива B. Все элементы массива неотрицательные числа, не превышающие 10¹⁸.

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

Примеры

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

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

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

27309#27309

Вы должны реализовать алгоритм или структуру данных, эффективно реализующих следующие запросы:

1)Добавление в массив элемента

2)Извлечение k-того по величине элемента массива (первым по величине будет считаться наименьший элемент)

Гарантируется, что каждый элемент встречается в массиве всего один раз

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

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

Далее вводится натуральное m - количеств запросов.

В каждой из следующих m строк содержится слово "add" или "get" и целое число k.

Все численные значения по модулю не превосходят 1000.

В первом случае вы должны дополнить массив элементом со значением k. Иначе - вывести k-тый элемент отсортированного текущего массива (индексация с единицы).

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

Вы должны ответить на запрос извлечения k-того элемента массива, а именно вывести его значение на экран.

Двоичное дерево поиска Порядковые статистики

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

Cow Curling#27300

В коровий кёрлинг вовлечены две команды, каждая из которых двигает N тяжёлых камней (3 <= N <= 50,000) по льду. В конце игры имеется 2N камней на льду, каждый из которых расположен в различной точке

плоскости.

Подсчёт очков в коровьем кёрлинге ведётся следующим образом:

Камень считается «захваченным», если он содержится внутри треугольника, по углам которого находятся камни противника (камень, который находится на границе такого треугольника, также считается захваченным). Счёт команды есть количество камней команды противника, которые «захвачены».

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

INPUT FORMAT:

* Строка 1: Целое число N.

* Строки 2..1+N: Каждая строка содержит 2 целых числа, указывающих x и y координаты камня команды A (каждая координата лежит в диапазоне -40,000 .. +40,000).

* Строки 2+N..1+2N: Каждая строка содержит 2 целых числа, указывающих x и y координаты камня команды B (каждая координата лежит в диапазоне -40,000 .. +40,000).

OUTPUT FORMAT:

* Строка 1: Два разделённых пробелом целых числа, представляющих счета команд A и B

SAMPLE:

Ввод	Вывод
4 0 0 0 2 2 0 2 2 1 1 1 10 -10 3 10 3	1 2

INPUT DETAILS:

У каждой команды по 4 камня.

Команда A имеет камни (0,0), (0,2), (2,0), (2,2).

Команда B имеет камни (1,1), (1,10), (-10,3), (10,3).

OUTPUT DETAILS:

Команда A захватила камень противника в точке (1,1).

Команда B захватила камни противника в точках (0,2) и (2,2).

Вычислительная геометрия Динамическое программирование Структуры данных

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