Идеи

13 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Mowing the Field#90386
Фермер Джон косит траву. Он перемещает комбайн один раз в день. В день 1 он начинает в позиции \((x_1, y_1)\) и в день \(d\) перемещается по прямой в позицию \((x_d, y_d)\), двигаясь или горизонтально или вертикально по 2D-карте своей фермы. То есть либо \(x_d = x_{d-1}\), либо \(y_d = y_{d-1}\). ФД чередует в последовательные дни горизонтальные и вертикальные участки. Он косит довольно медленно, поэтому может такое случится, что когда он вернётся в позицию, там уже снова вырастет трава. Точнее, если в какой-то ячейке трава была скошена в день \(d\), то она повторно вырастет в день \(d + T\), поэтому если ФД попал в какую-то ячейку, в которой уже был не менее, чем \(T\) днями раньше, то ему придётся снова косить там траву. ФД хочет посчитать, сколько раз такое случится.

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

ФОРМАТ ВВОДА (файл mowing.in):

Первая строка ввода содержит \(N\) (\(2 \leq N \leq 100,000\)) и \(T\) (\(1 \leq T \leq N\), \(T\) even). Следующие \(N\) строк описывают позицию комбайна в дни \(1 \ldots N\). i-ая из этих строк содержит целые числа \(x_i\) \(y_i\) (неотрицательные целые не более 1,000,000,000).

ФОРМАТ ВЫВОДА (файл mowing.out):

Выведите количество точек пересечения, описанных выше.

Отрезки
—Войти и решать
It's Mooin' Time III#90314

Беси анализирует строку из \(N\) (\(3 \leq N \leq 10^5\)) маленьких латинских букв \(s_1s_2 \ldots s_N\). Эльза рассматривает строку \(t\), содержащую три символа как MOO если \(t_2 = t_3\) и \(t_2 \neq t_1\).

Триплет \((i, j, k)\) валидный, если \(i < j < k\) и строка \(s_i s_j s_k\) формирует MOO. Для этого триплета ФД выполняет следующее, чтобы вычислить его величину

  • ФД сгибает строку \(s\) на 90-градусов в индексе \(j\)
  • Величина триплета - удвоенная площадь \(\Delta ijk\).

Другими словами, величина триплета есть \((j-i)(k-j)\).

Беси задаёт Вам \(Q\) (\(1 \leq Q \leq 3 \cdot 10^4\)) вопросов. В каждом вопросе она даёт Вам два целых числа \(l\) и \(r\) (\(1 \leq l \leq r \leq N\), \(r-l+1 \ge 3\)) и просит Вас определить максимальную величину среди всех валидных триплетов \((i, j, k)\) таких, что \(l \leq i\) и \(k \leq r\). Если валидных триплетов нет, выведите \(-1\).

Решение задачи может потребовать использовать 64-й целый тип (например, "long long" in C/C++).

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит два целых числа \(N\) и \(Q\).

Следующая строка содержит символы \(s_1 s_2, \ldots s_N\).

Последующие \(Q\) строк содержат по два целых числа \(l\) и \(r\), обозначающих запрос.

ФОРМАТ ВЫВОДА (на экран / stdout):

Выведите ответ на каждый вопрос в отдельной строке.
Отрезки
—Войти и решать
Grass Segments#90276

Беси посадила траву на положительной вещественной прямой. У неё есть \(N\) (\(2\le N\le 2\cdot 10^5\)) различных сортов травы. И она посадит траву \(i\)-го сорта на интервале \([\ell_i, r_i]\) (\(0 < \ell_i < r_i \leq 10^9\)).

Известно, что сорт \(i\) растёт лучше, если есть некоторый сорт \(j\) (\(j\neq i\)) такой, что сорт \(j\) и сорт \(i\) перекрываются на длину не менее \(k_i\) (\(0 < k_i \leq r_i - \ell_i\)). Беси хочет для каждого сорта \(i\) вычислить количество таких of \(j\neq i\), что сорты \(j\) и \(i\) перекрываются на длину не менее \(k_i\).

ФОРМАТ ВВОДА (с клавиатуры / stdin):

Первая строка содержит число \(N\).

Каждая из последующих \(N\) строк содержит три разделённых одиночными пробелами целых числа \(\ell_i\), \(r_i\), \(k_i\).

ФОРМАТ ВЫВОДА (на экран / stdout):

Ответы для всех сортов на отдельных строках.

SCORING:

  • Тесты 4-5: \(N \leq 5000\)
  • Тесты 6-11: \(k\) одинаковое для всех интервалов
  • Тесты 12-20: Нет дополнительных ограничений..

В дополнение, в тестах 5, 7, ..., 19, \(r_i \leq 2N\) for all \(i\).

Автор: Benjamin Qi

ОтрезкиПрефиксные суммы(минимумы, ...)Сортировка событий
—Войти и решать
Sleepy Cow Herding#90058
\(N\) коров Фермера Джона бродят далеко от фермы. Ваша задача - собрать их в стадо.

Главное поле фермы представлено прямой, на которой каждая корова занимает некоторое положение в целочисленной координате. Изначально все \(N\) коров находятся в различных позициях. ФД хочет, чтобы они заняли соседние позиции (например 3,4,5,6,7,8).

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

Определите минимальное и максимальное количество таких перемещений, чтобы коровы заняли \(N\) последовательных позиций.

ФОРМАТ ВВОДА (файл herding.in):

Первая строка ввода содержит \(N\) (\(3 \leq N \leq 10^5\)). Каждая из следующих \(N\) строк содержит целое число (в интервале \(1 \ldots 10^9\)) - местоположение коровы.

ФОРМАТ ВЫВОДА (файл herding.out):

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

Жадный алгоритмЗадача на реализациюОтрезки
—Войти и решать
Trapped in the Haybales (Silver)#89961
Фермер Джон получил груз из \(N\) больших стогов сена (\(1 \le N \le 100,000\)), и разместил стога в различных позициях вдоль дороги, соединяющей амбар с его домом. Каждый стог с номером \(j\) имеет размер \(S_j\) и находится в уникальной позиции \(P_j\) определяющей его положение вдоль одномерной дороги. Корова Беси расположена в настоящий момент в позиции \(B\),где нет стога сена. Беси может передвигаться вдоль дороги вплоть до позиции, где расположен стог сена, но она не может проходить эту позицию. Как исключение, если она движется в некотором направлении \(D\) единиц расстояния, то она набирает скорость достаточную чтобы уничтожить любой стог сена с размером строго меньше, чем \(D\). Конечно после того как она сделает это, она может бежать дальше к другим стогам и уничтожать их аналогичным способом.

ФД перекрасил дои и амбар и хочет быть уверенным, что Беси не доберётся ни туда, ни туда (Корова и свежая краска не есть хорошая комбинация!). Соответственно, ФД хочет быть уверенным, что Беси никогда не выйдет ни за самый левый, ни за самый правый стог. ФД может добавить сена в один стог по своему выбору, так чтобы гарантировать, что Беси не выберется. Пожалуйста, помогите ему определить минимальное количество дополнительного размера, который он должен добавить к некоторому стогу сена, чтобы гарантировать, что Беси останется в ловушке.

ФОРМАТ ВВОДА (файл trapped.in):

Первая строка ввода содержит \(N\) и начальную позицию Беси \(B\). Каждая из последующих \(N\) строк описывает стог и содержит два целых числа, определяющих его размер и местоположение. Все размеры и положения находятся в диапазоне \(1\ldots 10^9\).

ФОРМАТ ВЫВОДА (файл trapped.out):

Выведите одно целое число, определяющее минимальное количество сена, которое должен добавить ФД чтобы Беси не выбралась из ловушки. Выведите -1, если это сделать невозможно.

Жадный алгоритмОтрезкиреализация
—Войти и решать
Photo#89909

ФД хочет сфотографировать все свои N коров (2 <= N <= 1,000,000,000), которые выстроились в линию и последовательно пронумерованы от 1 до N. Каждая фотография может вместить некоторый последовательный диапазон коров, и ФД хочет, чтобы каждая корова была, как минимум, на одной фотографии.
К несчастью, имеется K недружественных пар коров (1 <= K <= 1000), которые отказываются находиться на одной фотографии. Вам даны позиции этих недружественных пар коров, определите минимальное количество фотографий, которые придется сделать ФД.
PROBLEM NAME: photo
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа, N и K.
* Строки 2..K+1: Строка i+1 содержит два целых числа, Ai и Bi, указывающих, что коровы на позициях Ai и Bi недружественные, и поэтому не могут быть на одной и той же фотографии.
Формат выходных данных
* Файл 1: Одно целое число, указывающее минимальное количество фотографий, которые должен сделать ФД
Примечание
ФД должен сделать 3 фотографии: - Одна в диапазоне от 1 до 2. - Одна в диапазоне от 3 до 5. - Одна в диапазоне от 6 до 7.
Отрезки
—Войти и решать
Painting the Fence#89881

Корова Беси красит забор Фермеру Джону. Беси начинает в позиции 0 и выполняет последовательность из N инструкций. (1 <= N <= 100,000) вида "10 L", что означает покрасить 10 единиц влево и "15 R", что означает покрасить 15 единиц вправо.
Бесси может уйти не далее чем на 1,000,000,000 единиц от исходной точки.
По имеющей инструкции ФД хочет узнать область забора, которая покрашена как минимум двумя слоями краски.

PROBLEM NAME: paint
Формат входных данных
* Строка 1: Целое N
* Строки 2..1+N: Каждая строка описывает одну из N инструкций
Формат выходных данных
* Строка 1: Общая часть, покрашенная как минимум 2 слоями краски.
Примечание
6 единиц покрыто как минимум 2 слоями краски. Это интервалы: [-11,-8], [-4,-3], [0,2].

Отрезки
—Войти и решать
Overplanting (Silver)#89822

Фермер Джон купил новую машину, которая умеет садить траву в прямоугольном регионе со сторонами, параллельными осям координат. К несчастью, эта машина однажды сломалась и посадила траву не в одном, а в N (1 <= N <= 1000) различных регионах, некоторые из которых могут даже перекрываться.
По заданным прямоугольным регионам, засаженным травой, помогите ФД определить общую площадь, покрытую травой.
PROBLEM NAME: planting
Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Каждая строка содержит четыре разделенных одиночными пробелами целых числа x1 y1 x2 y2 указывающих прямоугольный регион с верхним - левым углом (x1,y1) и нижним – правым углом (x2,y2). Все координаты – целые числа в диапазоне -10^8...10^8..
Формат выходных данных
* Строка 1: Общая площадь, покрытая травой. Заметим, что общая площадь может быть настолько большой, что не поместиться в 32-битное целое.
Отрезки
—Войти и решать
Overplanting (Bronze)#89816
Фермер Джон купил новую машину, которая умеет садить траву в прямоугольном регионе со сторонами, параллельными осям координат. К несчастью, эта машина однажды сломалась и посадила траву не в одном, а в N (1 <= N <= 10) различных регионах, некоторые из которых могут даже перекрываться.
По заданным прямоугольным регионам, засаженным травой, помогите ФД определить общую площадь, покрытую травой.
PROBLEM NAME: planting

Формат входных данных
* Строка 1: Целое число N.
* Строки 2..1+N: Каждая строка содержит четыре разделенных одиночными пробелами целых числа x1 y1 x2 y2 указывающих прямоугольный регион с верхним - левым углом (x1,y1) и нижним – правым углом (x2,y2). Все координаты – целые числа в диапазоне -10,000...10,000.

Формат выходных данных
* Строка 1: Общая площадь, покрытая травой.
Сжатие координатСканирующая прямая
✓ 3✗ 8—Войти и решать
Необычная сортировка#60876

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

Для этого Магане может один раз выбрать произвольный набор различных позиций в массиве и заменить элементы на этих позициях на противоположные, то есть умножить их на \(-1\). Например, чтобы сделать массив \([-4, 4, 1, 3, -10]\) отсортированным, она может умножить на \(-1\) числа на позициях \(2\) и \(5\), и получить массив \([-4, -4, 1, 3, 10]\).

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

Помогите ей с этой задачей! Поскольку итоговое количество способов может быть слишком большим, найдите ответ по модулю \(998244353\).

В первой строке ввода записано целое число \(n\) — количество элементов в массиве (\(1 \leqslant n \leqslant 10^6\)).

Формат входных данных
Во второй строке через пробел перечислены \(n\) целых чисел \(a_1\), \(a_2\), …, \(a_n\) — элементы массива (\(-10^9 \leqslant a_i \leqslant 10^9\)).

Формат выходных данных
Выведите одно число — количество способов отсортировать массив указанным образом (по модулю \(998244353\)).

 

Алгоритмы сортировкиИдеиЛинейные алгоритмы
✓ 2✗ 11—Войти и решать
Цирковое выступление#57844

Недавно в город приехал известный цирк. Всего в этом цирке \(n\) акробатов, и в этот раз в честь проведения СПбКОШП 2022 они подготовили особенный номер.

Известно, что \(i\)-й акробат имеет рост \(a_i\) и вес \(b_i\). Любые три акробата могут собраться вместе и показать необычный трюк. Если трюк показывают акробаты с номерами \(i\), \(j\) и \(k\), то эффектность трюка оценивается как \(a_i b_j + a_j b_k + a_k b_i\).

Тренер акробатов считает упорядоченную тройку акробатов \((i, j, k)\) хорошей, если эффектность их трюка будет не меньше, чем если они расположатся в обратном порядке \((k, j, i)\).

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

Формат входных данных
В первой строке ввода дано целое число \(n\) — количество акробатов в цирке (\(3 \leqslant n \leqslant 1000\)).

В \(i\)-й из следующих \(n\) строк через пробел даны целые числа \(a_i\) и \(b_i\) — рост и вес \(i\)-го акробата (\(1 \leqslant a_i, b_i \leqslant 10^9\)).

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

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

ИдеиМногоугольники. Выпуклые оболочки
✓ 3✗ 3—Войти и решать
Памятник#56262

Одна из центральных площадей Архангельска замощена прямоугольными плитками размера \(1 \times k\). Если ввести систему координат, так что левый нижний угол одной из плиток будет иметь координаты \((0, 0)\), то левые нижние углы плиток будут иметь координаты \((i \cdot k+j,j)\) для всех целых \(i\) и \(j\).

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

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

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

Входные данные
Первая строка входных данных содержит два числа \(n\) и \(k\) — количество вершин в основании памятника и размер плитки.

Каждая из последующих \(n\) строк содержит два целых числа \(x_i\), \(y_i\) — координаты \(i\)-й вершины основания. Координаты перечислены в порядке обхода против часовой стрелки.

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

Замечание

Задачи на моделированиеОтрезкиреализация
✓ 1✗ 0—Войти и решать
Прогулка котов#46436
Вдоль прямой улицы через каждый метр расположены фонарные столбы. На каждом столбе написан номер метра, на котором он расположен. Первый столб расположен в начале улицы и имеет номер 0. 

Код Рудольф гуляет вдоль улицы, от фонаря с номером a до фонаря с номером b. Полосатый кот Ихмиллион прогуливается от фонаря с номером c до фонаря с номером d. Определите, количество фонарных столбов, мимо которых проходя оба кота.



Входные данные
Вводятся четыре числа в одной строке через пробел: a, b, c, d (0 < a, b, c, d <= 100). 

Выходные данные
Выведите ответ на задачу.
 
Примеры
№ Входные данные Выходные данные Пояснение
1 5 8 6 2 2 Рудольф прогуливается от фонаря с номером 5 до  8-го фонаря и обратно, а Ихмиллион со 6-го по 2-й и обратно. Одновременно оба кота прогуливаются мимо фонарей с номерами 5 и 6. Всего фонарей два.
2 5 3 7 9 0 Нет общих фонарей, мимо которых прогуливаются оба кота.
ОтрезкиПересечение множеств
✓ 1✗ 4—Войти и решать
Поделиться
Класснуть