В парке города Питсбурга есть чудесная аллея, состоящая из N посаженных в один ряд деревьев, каждое одного из K сортов. В связи с тем, что Питсбург принимает открытый чемпионат Байтландии по программированию, было решено построить огромную арену для проведения соревнований. Так, согласно этому плану вся аллея подлежала вырубке. Однако министерство деревьев и кустов воспротивилось этому решению, и потребовало оставить некоторые из деревьев в покое. Согласно новому плану строительства все деревья, которые не будут вырублены, должны образовывать один непрерывный отрезок, являющийся подотрезком исходного. Каждого из K видов деревьев требуется сохранить хотя бы по одному экземпляру. На вас возложена задача найти отрезок наименьшей длины, удовлетворяющий указанным ограничениям.
В первой строке входного файла находятся два числа N и K ( 1 ≤ N , K ≤ 250000 ). Во второй строке входного файла следуют N чисел (разделенных пробелами), i -ое число второй строки задает цвет i -ого слева дерева в аллее. Гарантируется, что присутствует хотя бы одно дерево каждого цвета
В выходной файл выведите два числа, координаты левого и правого концов отрезка минимальной длины, удовлетворяющего условию. Если оптимальных ответов несколько, выведите любой.
5 3 1 2 1 3 2
2 4
6 4 2 4 2 3 3 1
2 6
На одной из планет, под названием TheBestWorld, живут много умных людей. Эта планета также известна своими двумя конкурирующими школами супергероев. Каждый малыш, живущий на этой планете, мечтает стать супергероем, но не у всех это получается.
Ученики разных школ всегда недолюбливали друг друга. И иногда дело даже доходило до того, как супергерои начали применять свои геройские силы для выяснения отношений.
В этом мире случилось несчастье. На TheBestWorld нападают темные силы. У генерала главнокомандующего армией супергероев есть в распоряжении n + m супергероев, из них n — выпускники первой школы, m — второй. Главнокомандующий подсчитал количество супергероев k , которые смогут спасти лучшее, что у них есть, — планету.
На первый взгляд кажется, что главнокомандующему не понадобится помощь в выборе супергероев, но он вспомнил, что супергерои из разных школ раздражают друг друга. Но это происходит только тогда, когда два супергероя из разных школ находятся на расстоянии меньше d . Если такую пару героев позвать спасать мир, они не смогут продуктивно делать свою работу.
Проблема в том, что генерал забыл искомое d . Вам известны координаты каждого из супергероев. Генерал просит вас вычислить максимальное d , при котором он все еще может спасти мир. И выдать список супергероев, которые спасут мир при данном d .
В первой строке входного файла заданы три числа n , m и k ( 1 ≤ k , n , m ≤ n + m ≤ 200 ) — количество супергероев, выпустившихся из первой и второй школы, и количество супергероев, которое необходимо, чтобы спасти мир, соответственно. Следующие n + m строк описывают супергероев: в каждой строке заданы два целых числа — текущие координаты супергероя. Первые n строк содержат информацию о выпускниках первой школы, следующие m — о выпускниках второй школы. Все координаты не превышает по модулю 10000 . Известно, что никакие два супергероя не стоят в одной точке.
В первую строку выходного файла выведите одно вещественное число: максимальное значение d , которое позволяет спасти мир, либо -1, если при любом значении d мир можно спасти. Относительная или абсолютная погрешность вашего ответа не должна превышать 10 −6 . В следующих k строках выведите список номеров супергероев по одному числу в строке, которых можно взять при данном d , либо, если спасти мир можно при любом d , выведите список героев, которые позволяет спасти мир вне зависимости от d . Супергерои нумеруются числами от 1 до n + m в том порядке, в котором они идут во входном файле.
2 3 4 1 1 1 2 1 3 1 4 1 5
2.000000000000000000 1 3 4 5
1 1 2 1 1 1 10
9.000000000000000000 1 2
Фермер Николай нанял двух лесорубов: Дмитрия и Федора, чтобы вырубить лес, на
месте которого должно быть кукурузное поле. В лесу растут \(X\) деревьев.
Дмитрий срубает по A деревьев в день, но каждый \(K\)-й день он отдыхает и не срубает
ни одного дерева. Таким образом, Дмитрий отдыхает в \(K\)-й, 2\(K\)-й, 3\(K\)-й день, и т.д.
Федор срубает по B деревьев в день, но каждый \(M\)-й день он отдыхает и не срубает ни
одного дерева. Таким образом, Федор отдыхает в \(M\)-й, 2\(M\)-й, 3\(M\)-й день, и т.д.
Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не
отдыхает, они срубают \(A\) + \(B\) деревьев, в дни, когда отдыхает только Федор — \(A\) деревьев, а в
дни, когда отдыхает только Дмитрий — \(B\) деревьев. В дни, когда оба лесоруба отдыхают, ни
одно дерево не срубается.
Фермер Николай хочет понять, за сколько дней лесорубы срубят все деревья, и он
сможет засеять кукурузное поле.
Требуется написать программу, которая по заданным целым числам \(A\), \(K\), \(B\), \(M\) и \(X\)
определяет, за сколько дней все деревья в лесу будут вырублены.
Входной файл содержит пять целых чисел, разделенных пробелами: \(A\), \(K\), \(B\), \(M\) и \(X\) (1 ≤ \(A\), \(B\) ≤ \(10^9\) , 2 ≤ \(K\), \(M\) ≤ 1018, 1 ≤ \(X\) ≤ 1018).
Выходной файл должен содержать одно целое число — искомое количество дней.
В приведенном примере лесорубы вырубают 25 деревьев за 7 дней следующим
образом:
* 1-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 5 деревьев;
* 2-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 10
деревьев;
* 3-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 12 деревьев;
* 4-й день: Дмитрий отдыхает, Федор срубает 3 дерева, итого 15 деревьев;
* 5-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 20
деревьев;
* 6-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 22 дерева;
* 7-й день: Дмитрий срубает 2 дерева, Федор срубает оставшееся 1 дерево, итого
все 25 деревьев срублены.
Внимание! Тест из примера не подходит под ограничения для подзадач 2 и 3, но
решение принимается на проверку только в том случае, если оно выводит правильный ответ
на тесте из примера. Решение должно выводить правильный ответ на тест даже, если оно
рассчитано на решение только каких-либо из подзадач 2 и 3
Подзадача 1 (32 балла)
1 ≤ \(X\) ≤ 1000, 1 ≤ \(A\), \(B\) ≤ 1000, 2 ≤ \(K\), \(M\) ≤ 1000
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 2 (10 баллов)
1 ≤ \(X\) ≤ 1018
\(X\) < \(K\)
\(X\) < \(M\)
При решении этой подзадачи можно считать, что лесорубы не отдыхают.
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 3 (10 баллов)
1 ≤ \(X\) ≤ 1018
Дополнительно к приведенным ограничениям выполняется условие \(K\) = \(M\).
Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 4 (48 баллов)
1 ≤ \(X\) ≤ 1018, 1 ≤ \(A\), \(B\) ≤ \(10^9\), 2 ≤ \(K\), \(M\) ≤ 1018
В этой подзадаче 16 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест
начисляются независимо.
2 4 3 3 25
7
Крешо купил вкуснейший сыр с перцем, но Степану перец не нравится, поэтому он хочет отрезать кусок, на котором не было бы перца. Сыр имеет форму выпуклого многоугольника, а каждая перчинка является точкой внутри него. Степан режет сыр только 1 раз. Он выбирает две вершины многоугольника, не являющиеся смежными, и режет по диагонали, соединяющей их. Затем Степан забирает ту из получившихся частей, на которой нет перца (ни внутри, ни на границе).
Рисунок соответствует первому тесту. Пунктирной линией показан разрез Степана.
Напишите программу, которая определит, может ли Степан отрезать кусок без перца. Если он может это сделать, выведите максимальную площадь куска, который может отрезать Степан.
Первая строка входного файла содержит одно целое число N — количество вершин в многоугольнике. Каждая из следующих N строк содержит два числа x i и y i — координаты i -й вершины. Следующая строка содержит одно число M — количество перчинок. Каждая из следующих M строк содержит два числа x i и y i — координаты i -й перчинки.
Вершины многоугольника заданы в порядке обхода против часовой стрелки и образуют выпуклый многоугольник. Никакие две подряд идущие стороны не параллельны.
Все перчинки расположены в различных точках и внутри многоугольника (они не расположены на стороне или снаружи многоугольника).
Выведите одно число — удвоенную максимальную площадь (это число всегда целое). Если отрезать кусок без перца невозможно, выведите 0.
Система оценки:
Во всех подзадачах координаты от - 10 9 до 10 9 .
5 0 1 3 0 4 2 2 3 0 3 3 2 1 3 1 3 2
4
Петя участвует в конкурсе, в котором разыгрывается \(n\) призов. Призы пронумерованы от 1 до \(n\).
По итогам конкурса участник может набрать от 2 до \(n\) баллов. Если участник наберет \(k\) баллов, то он получит один из призов с номером от 1 до \(k\). Перед тем, как участник выберет свой приз, ведущий конкурса удаляет один из призов из списка. Затем участник может выбрать любой приз из оставшихся \(k\) – 1.
Список призов стал известен Пете. Петя определил для каждого приза его ценность, для \(i\)-го приза она задается целым числом \(a_i\) .
Требуется написать программу, которая по заданным ценностям призов определяет для каждого \(k\) от 2 до \(n\), приз с какой максимальной ценностью гарантированно достанется Пете, если он наберет в конкурсе \(k\) баллов.
Первая строка входного файла содержит число \(n\) (\(2 \le n \le 100 000\)). Вторая строка этого файла содержит n целых чисел: \(a_1, a_2, …, a_n\) (\(1 \le a_i ≤ 10^9\) ).
Выходной файл должен содержать одну строку, содержащую \(n\) – 1 целых чисел: для каждого \(k\) от 2 до \(n\) должна быть выведена ценность приза, который достанется Пете, если он наберет \(k\) баллов.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
\(n \le 100\)
\(n \le 5000\)
\(n \le 100000\)
5 1 3 4 2 5
1 3 3 4