--->
90 задач
<---
Источники
В одной Очень Известной Летней Школе наиболее популярным видом спорта является волейбол. Для каждого из \(N\) школьников известно его умение играть в волейбол. Перед началом занятий школьников необходимо распределить между двумя тренерами.
Тренеры сочли справедливым следующий алгоритм разделения на две группы. Сначала они выбирают два целых числа \(p\), \(q\) (\(0 < p \le q \le N\)). Затем первый берет себе \(p\) лучших школьников, после чего оба тренера, начиная со второго, берут по очереди по \(q\) лучших школьников из оставшихся, пока их количество не меньше \(q\). В конце очередной тренер просто берет всех оставшихся.
Оба тренера заинтересованы в наиболее справедливом распределении школьников между группами. Поэтому они стремятся найти такие \(p\) и \(q\), чтобы разница суммарных умений между двумя группами школьников оказалась минимальной. При этом, вообще говоря, не обязательно, чтобы количество школьников в каждой из групп было одинаковым.
Помогите тренерам подобрать такие "справедливые" значения \(p\) и \(q\) (\(0 < p \le q \le N\)), при которых разница в суммарных умениях образованных групп школьников по абсолютной величине будет минимальна.
В первой строке входного файла записано единственное целое число \(N\). Во второй строке содержатся \(N\) неотрицательных целых чисел, не превосходящих \(10^9\) - умения школьников играть в волейбол.
Выведите искомые целые значения \(p\) и \(q\) (\(0 < p \le q \le N\)). Если искомых пар несколько, то выведите любую из них.
Тесты состоят из четырёх групп.
8 5 3 3 3 3 3 7 1
1 2
На плоскости задан прямоугольник размером \(W\times H\), и \(N\) отмеченных точек внутри него. Требуется найти квадрат максимального размера:
со сторонами, параллельными сторонам прямоугольника;
не содержащий отмеченных точек строго внутри себя (но, возможно, содержащий отмеченные точки на границе);
лежащий внутри прямоугольника.
Первая строка входного файла содержит числа \(N\) — количество отмеченных точек, \(W\) — ширину прямоугольника и \(H\) — высоту прямоугольника (\(1 \leq N \leq 3 * 10^4\), \(0 \leq W, H \leq 10^6\)). Следующие \(N\) строк содержат координаты отмеченных точек \(X_i\), \(Y_i\) (целые числа, \(0 \leq X_i \leq W\), \(0 \leq Y_i \leq H\)). Система координат введена так, что вершины прямоугольника имеют координаты \((0, 0)\), \((W, 0)\), \((0, H)\), \((W, H)\).
Выведите в выходной файл одно число — длину стороны максимального искомого квадрата.
7 10 7 3 2 4 2 7 0 7 3 4 5 2 4 1 7
4
1 10 10 5 5
5
Вам задана таблица целых чисел
| \(a_{1, 1}\) | \(a_{1, 2}\) | ... | \(a_{1, n}\) |
| \(a_{1, 1}\) | \(a_{2, 2}\) | ... | \(a_{2, n}\) |
| ... | ... | ... | ... |
| \(a_{m, 1}\) | \(a_{m, 2}\) | ... | \(a_{m, n}\) |
Первая строка входного файла содержит числа \(m\) и \(n\) — размер таблицы (\(1 \leq m,n \leq 500\)). Следующие m строк содержат по n целых чисел каждая - \(a_{ij}\). Все числа между \(-2^{31}\) и \(2^{31}-1\). Далее следует \(q\) — количество запросов (\(1 \leq q \leq 200000\)). Следующие \(q\) строк содержат по четыре целых числа: \(x_{i1}\), \(y_{i1}\), \(x_{i2}\) и \(y_{i2}\) (\(1 \leq x_{i1} \leq x_{i2} \leq m\), \(1 \leq y_{i1} \leq y_{i2} \leq n\)).
Выведите \(q\) чисел — для каждого запроса выведите минимальное значение в соответствующем прямоугольнике.
Обратные задачи представляют собой быстро развивающуюся область информатики. В отличии
от классической постановки задачи, где по заданным исходным данным \(D\) требуется решить некоторую оптимизационную задачу \(P\), в обратной задаче по заданной задаче \(P\) и результату вычисления
\(R\) требуется подобрать исходные данные \(D\), на которых достигается этот результат. В этой задаче
вам предлагается решить обратную задачу к задаче о минимуме на отрезке (range minimum query,
RMQ).
Пусть задан массив \(a[1..n]\). Ответ на запрос о минимуме на отрезке \(Q(i, j)\) — это минимальное
среди значений \(a[i]\), ..., \(a[j]\). Вам дано \(n\) и последовательность запросов о минимуме на отрезке с
ответами. Восстановите исходный массив \(a\).
Первая строка входного файла содержит \(n\) — размер массива, и \(m\) — количество запросов (\(1 \leq n, m \leq 100000\)). Следующие \(m\) строк содержат по три целых числа: числа \(i\), \(j\) и \(q\) означают, что \(Q(i, j) = q\) (\(1 \leq i \leq j \leq n\), \(-2^{31} \leq q \leq 2^{31} - 1\)).
Если входные данные несовместны, то есть искомого массива a не существует, выведите
"inconsistent" на первой строке выходного файла.
В противном случае выведите “consistent” на первой строке выходного файла. Вторая строка
должна содержать сам массив. Элементы массива должны быть целыми числами между \(2^{31}\) и \(2^{31}-1\). Если решений несколько, выведите любое.
Баллы за эту задачу будут начислены только если решение проходит все тесты
3 2 1 2 1 2 3 2
consistent 1 2 2
3 3 1 2 1 1 1 2 2 3 2
inconsistent
Знаете ли вы, почему четвертый этаж заперт и там не останавливается лифт? Потому что на самом деле четвертый, запертый, этаж, где не останавливается лифт, содержит бесконечное количество комнат, пронумерованных натуральными числами. На этот этаж регулярно приезжают дети, каждый из которых заранее выбрал, в какую комнату он хочет заселиться. Если выбранная комната оказывается свободна, то ребенок занимает ее, в противном случае он занимает первую свободную комнату с бóльшим номером.
Кроме того, некоторые дети уезжают в середине смены. Сразу после отъезда ребенка его комната становится доступна для заселения следующего.
Промоделируйте работу преподавателей, ответственных за четвертый этаж и научитесь быстро сообщать приезжающим детям, какую комнату им следует занимать.
Первая строка входного файла содержит натуральное число \(n\) — количество прибытий и отъездов, происходящих в течение смены (\(1 \le n \le 100\,000\)).
Следующие \(n\) строк содержат информацию об ЛКШатах. Число \(a > 0\) обозначает, что приехал школьник, желающий занять комнату номер \(a\) (\(1 \le a \le 100\,000\)). Число \(a < 0\) обозначает, что из комнаты номер \(|a|\) уехал школьник (гарантируется, что эта комната не была пуста).
Для каждого приезжающего школьника выведите одно натуральное число — номер комнаты, в которую он поселится.
6 5 5 5 -6 5 5
5 6 7 6 8