Темы --> Информатика --> Структуры данных
    Деревья(174 задач)
    Линейные структуры(59 задач)
    Корневая эвристика (sqrt декомпозиция)(14 задач)
    Разреженные таблицы (sparse table)(2 задач)
    Система непересекающихся множеств(16 задач)
    Хеш(35 задач)
    Персистентные структуры данных(2 задач)
---> 279 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 26 27 28 29 30 31 32 >> Отображать по:
#3350
Машинки (AB)
  
Темы: [Куча]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке содержаться три числа \(N\), \(K\) и \(P\) (\(1 \leq K \leq N \leq 100000\), \(1 \leq P \leq 500000\)). В следующих \(P\) строках записаны номера машинок в том порядке, в котором Петя захочет играть с ними.

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

Выведите единственное число: минимальное количество операций, которое надо совершить Петиной маме.

Примечание к примеру тестов

Операция 1: снять машинку 1
Операция 2: снять машинку 2
Операция 3: поднять машинку 2 и снять машинку 3
Операция 4: поднять машинку 3 или 1 и снять машинку 2

Примеры
Входные данные
3 2 7
1
2
3
1
3
1
2
Выходные данные
4
#3362
Максимальный квадрат
  

На плоскости задан прямоугольник размером \(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
#3366
Дятлы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Необходимо проверить отсутствие циклов

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

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

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

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

В первой строке содержатся три числа: \(N\) – количество дятлов (\(1 \leq N \leq 10^6\)), \(M\) – количество пар знакомых дятлов (\(1 \leq M \leq 10^7\)) и число \(K\) (\(1 \leq K \leq 2\times 10^6\)). Дятлы занумерованы от \(1\) до \(N\). В следующих \(M\) строках заданы два числа \(a_i\) и \(b_i\) (\(1 \leq a_i, b_i \leq N\)), задающие пару знакомых дятлов.

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

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

Примеры тестов

Примеры
Входные данные
3 2 10
1 2
1 3
Выходные данные
4
Входные данные
4 4 17
1 2
1 3
4 2
3 4
Выходные данные
0
#3389
Минимум в прямоугольнике
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
256 megabytes
Двумерное RMQ

Вам задана таблица целых чисел

\(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}\)
и последовательность запросов \(Q(x_{i1}, y_{i1}, x_{i2}, y_{i2})\). Для каждого запроса найдите минимальное значение среди значений \(a_{k,l}\), где \(x_{i1} \leq k \leq x_{i2}\) и \(y_{i1} \leq l \leq y_{i2}\).

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

Первая строка входного файла содержит числа \(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\) чисел — для каждого запроса выведите минимальное значение в соответствующем прямоугольнике.

#3391
Обратная задача для RMQ
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Обратные задачи представляют собой быстро развивающуюся область информатики. В отличии от классической постановки задачи, где по заданным исходным данным \(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
Страница: << 26 27 28 29 30 31 32 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест