Любимый всем кукольник Гепетто открыл новую пиццерию. Он хочет делать самую лучшую пиццу в городе, но не хочет иметь маленький ассортимент пицц.
Гепетто делает свои пиццы из N ингредиентов, пронумерованных от 1 до N . Всё было бы хорошо, но к сожалению он не может класть некоторые ингредиенты в одну пиццу.
Всего есть M пар ингредиентов, которые нельзя класть в одну пиццу. Помогите Гепетто узнать, сколько различных пицц он может cделать.
Первая строка содержит два целых числа N и M ( 1 ≤ N ≤ 20 , 0 ≤ M ≤ 400 ). Следующие M строк содержат по два различных чсла a и b , обозначающие, что класть ингредиенты a и b запрещено класть в одну пиццу ( 1 ≤ a , b ≤ N ).
Выведите одно число – ответ на задачу
В первом примере Гепетто может сделать пиццы из наборов {}, {1}, {2}, {3}, {1, 3}. Во втором примере он может использовать любую комбинацию ингредиентов. В третьем примере он может сделать пиццы из наборов {}, {1}, {2}, {3}.
3 2 1 2 2 3
5
3 0
8
3 3 1 2 1 3 2 3
4
Вы наверняка слышали легенду о Короле Артуре и Рыцарях Круглого Стола. Практически все версии этой истории указывают на то, что круглость Круглого Стола тесно связана с верой Артура в равенство среди рыцарей. Это ложь! На самом деле выбор Артура касательно формы стола вызван его детской травмой.
В реальности Артур был принужден убирать и мыть квадратные столы с юного возраста после того как на них играли в бирюльки. После соревнований по этой игре обычно на столе остается множество палочек, не касающихся друг друга. В духе соревнования, организаторы установили свод строгих правил для уборщиков. Точнее, палочки со стола должны быть убраны одна за другой путем их сдвига к ближайшему к уборщику краю стола. Они не должны вращаться и касаться других палочек в процессе перемещения.
В этой задаче представим стол на координатной плоскости как квадрат с противоположными вершинами в точках (0, 0) и (10000, 10000), где палочкам соответствуют прямые отрезки, лежащие внутри квадрата. Предположим, что Артур сидит у края стола, прилежащего к оси X. Тогда уборка палочек со стола сводится к передвижению их к оси X, покуда они не упадут со стола. Ваша задача - определить порядок уборки палочек со стола, который соответствует условиям из предыдущего абзаца.
Первая строка содержит единственное целое число N ( 1 ≤ N ≤ 5000 ) - количество палочек на столе. Каждая из следующих N строк содержит 4 целых числа x 1 , y 1 , x 2 , y 2 ( 0 ≤ x 1 , y 1 , x 2 , y 2 ≤ 10000 ), обозначающих крайние точки палочек.
В единственной строке выведите N целых чисел - номера палочек в том порядке, в котором они должны быть убраны со стола. Если существует несколько решений, выведите любое из них.
4 1 3 2 2 1 1 3 2 2 4 7 3 3 3 5 3
2 4 1 3
4 0 0 1 1 1 2 0 3 2 2 3 3 4 0 3 1
4 3 1 2
3 4 6 5 5 2 1 15 1 3 2 8 7
2 3 1
Известно, что в солнечной системе есть 8 планет и один планетоид. Мало кто знает, что ещё есть секретная планета, населенная медведями. Именно туда ассоциация Savez отправляет бравого генерала Хенрика для изучения медведей. Выяснилось, что медведи умеют телепортироваться. Расчётливый генерал Хедрик решил завербовать их в свою армию.
У одного медведя есть N строк (обозначим i -ю из них x i ). Исследования показывают, что количество раз, которое может телепортироваться медведь равно длине наибольшей подпоследовательности этих строк, удовлетворяющей такому правилу: строки x i и x j ( i < j ) могут принадлежать одной такой последовательности, если x i является и префиксом, и суффиксом x j .
Помогите уставшему от долгого полёта генералу Хендрику определить, сколько телепортаций сможет сделать данный медведь.
В первой строке содержится одно целое число N – количество строк, которые есть у медведя. В последующих N строках содержатся сами эти строки. Входной файл содержит не более двух миллионов символов.
Выведите одно число – ответ на вопрос любопытного генерала Хендрика.
В первом примере наибольшая последовательность A -> AA -> AAA В третьем примере наибольшая последовательность A -> A -> A или B -> B -> B
5 A B AA BBB AAA
3
5 A ABA BBB ABABA AAAAAB
3
6 A B A B A B
3
Юный Мирко решил купить куклу вуду. Учитывая что он крайне заинтересован в том, ктобы купить ее как можно дешевле, он начал отслеживать цены на кукол вуду каждый день. Его список состоит из цен на куклы в последние N дней, где a i обозначает цену куклы i дней назад.
Мирко думает, что нашел связь между средней ценой кукол в течении нескольких последовательных дней и ценой куклы в следующий день. Он хочет проверить свою догадку и задался вопросом: "Для данного числа P , сколько существует наборов последовательных дней в течении последних N дней, для которых средняя цена куклы в эти дни составляет не менее P ".
Два набора последовательных дней считаются различными, если у них отличается первый или последний день.
Первая строка содержит одно целое число N ( 1 ≤ N ≤ \(10^6\) ), количество дней в списке Мирко. Вторая строка содержит N целых чисел a i ( 0 ≤ a i ≤\(10^9\) ) - цены кукол в соответствующие дни. Третья строка содержит одно целое число P ( 0 ≤ P ≤\(10^9\) ).
Выведите одно целое число - ответ на вопрос Мирко для данного P .
3 1 2 3 3
1
3 1 3 2 2
5
3 1 3 2 3
1
В далекой стране есть N городов. Был избран новый премьер-министр. В настоящее время в этой стране нет ни одной дороги, поэтому премьер-министр решил модернизировать страну, соединив некоторые города с двусторонними автострадами в транспортные сети. Два города будут расположены в одной и той же сети, если можно добраться до одного города от другого, используя недавно построенные дороги. Каждый город будет расположен в какой-то сети. Каждая сеть состоит из одного или нескольких городов.
Города представлены в виде точек в двумерной системе координат. Дорога между двумя городами представлена в виде отрезка, соединяющего две точки, в которых расположены города. Длина дороги равна длине отрезка в километрах.
В настоящее время страна переживает экономический спад, поэтому премьер-министр решил, что из-за отсутствия бюджета они не будут строить дороги длиннее, чем D километров. Кроме того, премьер-министр радуется мелочам, поэтому он будет счастлив, если по крайней мере в одной сети будет существовать непустое подмножество городов (оно может включать все города в сети), где общая сумма жителей делится на К . Например, если K = 4 и есть сеть с городами, в которых есть 3 , 5 , 7 жителей соответственно, премьер-министр будет счастлив, потому что сумма жителей в первых двух городах равна 8 .
Помогите премьер-министру сократить расходы, определив минимальный уровень D , необходимый для того чтобы премьер-министр мог строить дороги и одновременно быть счастливым.
Первая строка ввода содержит целые числа N и K (1 ≤ N ≤ 50000, 1 ≤ K ≤ 30) . Каждая из следующих N строк содержит три целых числа x i ; y i ; k i (0 ≤ x i , y i , k i ≤ 100000000) , которые представляют координату x города, координату y и количество жителей в этом городе, соответственно. На входных данных не будет двух городов с одинаковыми координатами. Кроме того, не будет ни одного города, в котором число жителей делится на К .
Первая и единственная строка вывода должна содержать минимальную D с точностью до 3 -х знаков после запятой, такую, что можно строить дороги с условием, что премьер-министр будет счастлив. Входные данные будут такими, чтобы всегда было решение.
Объяснение первого примера: единственный способ удержать премьер-министра в счастливом настроение - все города должны находятся в одном округе. Минимальный D , для которого это возможно, равен 1.414 .
Объяснение второго примера: премьер-министр будет рад, если первые 5 городов находятся в одном округе. Если D = 5.657 , премьер-министр может соединить города 1, 2, 3, 5 с городом 4 . В этом случае сумма жителей в городах 1, 2, 3, 4, 5 составит 11 , что делится на 11 , Поэтому премьер-министр будет счастлив.
3 3 0 4 4 1 5 1 2 6 1
1.414
6 11 0 0 1 0 1 2 1 0 3 1 1 4 5 5 1 20 20 10
5.657
6 5 20 20 9 0 0 3 0 1 1 10 0 1 10 1 6 12 0 3
2.000