--->
39 задач
<---
Источники
Экзамен по берляндскому языку проходит в узкой и длинной аудитории. На экзамен пришло 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
У Коли сегодня день рождения! По этому случаю он решил после олимпиады сходить с друзьями в парк аттракционов. И какая удача — можно купить групповой билет сразу на всех, всего за 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
На экране расположены прямоугольные окна, каким-то образом перекрывающиеся (со сторонами, параллельными осям координат). Вам необходимо найти точку, которая покрыта наибольшим числом из них.
В первой строке входного файла записано число окон 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
Зевс подарил Артемиде, богине охоты, прямоугольный участок земли, чтобы вырастить лес. Левая сторона этого участка — это отрезок неотрицательного луча оси ординат, нижняя сторона — отрезок неотрицательного луча оси абсцисс, а (0, 0) — левый нижний угол участка. Зевс сказал Артемиде выращивать деревья только в точках с целыми координатами.
Артемида любит, когда лес выглядит естественно, и поэтому в её лесу любая прямая, проходящая через два дерева, не параллельна ни оси абсцисс, ни оси ординат.
Иногда Зевс хочет, чтобы Артемида вырубила для него деревья. Деревья должны быть вырублены так, чтобы выполнялись следующие условия:
Так как Артемида любит деревья, она хочет выполнить все условия таким образом, чтобы пришлось вырубить как можно меньше деревьев. Напишите программу, которая по информации о лесе и минимальному количеству деревьев 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
Дано 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 – координаты концов соответствующего отрезка(например, может быть пара 5 2). В последней строке 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