---> 39 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 2 3 4 5 6 7 8 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Экзамен по берляндскому языку проходит в узкой и длинной аудитории. На экзамен пришло N студентов. Все они посажены в ряд. Таким образом, позиция каждого человека задается координатой на оси Ox (эта ось ведет вдоль длинной аудитории). Два человека могут разговаривать, если расстояние между ними меньше или равно D. Какое наименьшее количество типов билетов должен подготовить преподаватель, чтобы никакие два студента с одинаковыми билетами не могли разговаривать? Выведите способ раздачи преподавателем билетов.

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

В первой строке входного файла содержится два целых числа N, D (1 ≤ N ≤ 10000; 0 ≤ D ≤ 106). Вторая строка содержит последовательность различных целых чисел X1, X2, ..., XN, где Xi (0 ≤ Xi ≤ 106) обозначает координату вдоль оси Ox i-го студента

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

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

Примеры
Входные данные
4 1
11 1 12 2
Выходные данные
2
1 1 2 2 
Входные данные
4 0
11 1 12 2
Выходные данные
1
1 1 1 1 
ограничение по времени на тест
1.5 second;
ограничение по памяти на тест
256 megabytes

У Коли сегодня день рождения! По этому случаю он решил после олимпиады сходить с друзьями в парк аттракционов. И какая удача — можно купить групповой билет сразу на всех, всего за S рублей!

Конечно, скидываться придется всем поровну. То есть, если Коля позовет k своих друзей, то каждому придется заплатить S / (k + 1) рублей (да, сам Коля тоже должен внести свою долю). При этом S не обязательно должно делиться на k + 1: главное — купить билет, а между собой друзья уж как-нибудь договорятся.

Всего у Коли n друзей, при этом i-й из них готов пойти с Колей в парк, если доля, которую ему придется заплатить не больше bi (больше денег у него просто с собой нет) и не меньше ai (иначе он решит, что Колин день рождения — это скучно, и пойдет играть в волейбол с Сережей).

Так что может так получиться, что всех позвать не удастся. Ну и ладно. Для каждого своего друга Коля знает число fi — количество веселья, который тот произведет, если его позвать.

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

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

В первой строке входного файлы содержится два целых числа: n и S (1 ≤ n ≤ 100000, 0 ≤ S ≤ 109) — количество друзей Коли и стоимость билета. В следующих n строках содержится по три целых числа: в i-й из этих строк находятся числа ai, bi и fi (0 ≤ ai ≤ bi ≤ S, 0 ≤ fi ≤ 109). Они означают, что i-го друга можно позвать на вечеринку, если доля, которую ему придется заплатить, лежит между ai и bi, и он произведет fi веселья.

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

В первой строке выходного файла выведите два числа: k (количество приглашенных на вечеринку друзей) и F (максимальное суммарное веселье, которое можно получить). Во второй строке выведите k чисел — номера друзей, которых нужно пригласить

Примеры
Входные данные
4 10
4 5 40
2 4 30
2 6 10
3 5 20
Выходные данные
2 50
2 4 
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

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

В первой строке входного файла записано число окон n (1 ≤ n ≤ 50 000). Следующие n строк содержат координаты окон x(1, i) y(1, i) x(2, i) y(2, i), где (x(1, i), y(1, i)) — координаты левого верхнего угла i-го окна, а (x(2, i), y(2, i)) — правого нижнего (на экране компьютера y растет сверху вниз, а x — слева направо). Все координаты — целые числа, по модулю не превосходящие 106.

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

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

Примеры
Входные данные
2
0 0 3 3
1 1 4 4
Выходные данные
2
1 3
Входные данные
1
0 0 1 1
Выходные данные
1
0 1
Входные данные
4
0 0 1 1
0 1 1 2
1 0 2 1
1 1 2 2
Выходные данные
4
1 1
Входные данные
5
0 0 1 1
0 1 1 2
0 0 2 2
1 0 2 1
1 1 2 2
Выходные данные
5
1 1
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Зевс подарил Артемиде, богине охоты, прямоугольный участок земли, чтобы вырастить лес. Левая сторона этого участка  — это отрезок неотрицательного луча оси ординат, нижняя сторона — отрезок неотрицательного луча оси абсцисс, а (0, 0) — левый нижний угол участка. Зевс сказал Артемиде выращивать деревья только в точках с целыми координатами.

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

Иногда Зевс хочет, чтобы Артемида вырубила для него деревья. Деревья должны быть вырублены так, чтобы выполнялись следующие условия:

  1. Зевс хочет, чтобы для него было вырублено хотя бы T деревьев.
  2. Чтобы потом построить прямоугольное футбольное поле для будущих футбольных успехов, Артемида должна вырубить все деревья внутри и на границе некоторой прямоугольной площадки, и ни одно дерево вне этой площадки.
  3. Стороны этой площадки должны быть параллельны осям координат.
  4. В двух противоположных углах площадки должны быть расположены деревья (которые будут вырублены).

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

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

Первая строка ввода содержит единственное число N — количество деревьев в лесу ( 1 < N ≤ 20 000 ). Вторая строка содержит единственное число T — минимальное количество деревьев, которые должны быть вырублены ( 1 < T N ). Следующие N строк описывают расположение деревьев. Каждая из этих строк содержит по два целых числа X и Y — координаты дерева ( 0 ≤ X , Y ≤ 64 000 ). Решения, работающие только для N < 5000 , будут оцениваться из 50 баллов.

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

Вывод должен содержать единственную строку, в которой записано два целых числа I и J , разделённых пробелом: Артемида должна вырубить деревья на площадке, углами которой будут деревья с номерами I и J (это те деревья, которые описаны в строках входного файла с номерами I + 2 и J + 2 ). Эти числа можно выводить в любом порядке. Возможно, есть несколько способов выбрать эти деревья, и в этом случае вы должны вывести любую из подходящих пар. Гарантируется, что во всех тестах жюри существует хотя бы одно решение.

Примеры
Входные данные
3
2
1 1
2 3
5 6
Выходные данные
1 2
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
64 megabytes

Дано n отрезков на числовой прямой и m точек на этой же прямой. Для каждой из данных точек определите, скольким отрезкам они принадлежат. Точка x считается принадлежащей отрезку с концами a и b , если выполняется двойное неравенство min ( a , b ) ≤ x max ( a , b ) .

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

Первая строка содержит два целых числа n (1 ≤ n ≤ 10 5 ) – число отрезков и m (1 ≤ m ≤ 10 5 ) – число точек. В следующих n строках по два целых числи a i и b i – координаты концов соответствующего отрезка. В последней строке m целых чисел – координаты точек. Все числа по модулю не превосходят 10 9

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

В выходной файл выведите m чисел – для каждой точки количество отрезков, в которых она содержится.

Примеры
Входные данные
3 2
0 5
-3 2
7 10
1 6
Выходные данные
2 0 
Входные данные
1 3
-10 10
-100 100 0
Выходные данные
0 0 1 

Страница: << 2 3 4 5 6 7 8 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест