Страница: << 1 2 3 4 5 6 7 >> Отображать по:
#111495
Столицы
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

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

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

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

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

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

Первая строка входного файла содержит два разделенных пробелом целых числа: количество городов в Триландии n и требуемое время в пути между столицами d (\(3 \leq n \leq 10^5\), \(1 \leq d < n\)). Каждая из последующих (n – 1) строк содержит описание одной дороги: пару разделенных пробелом различных целых чисел \(a_i\) и \(b_i\) — номера городов, которые соединены двусторонней дорогой (\(1 \leq a_i \leq n\), \(1 \leq b_i \leq n\), \(a_i \ne b_i\)). Каждая пара городов соединена не более чем одной дорогой.

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

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

Пояснения к тестам

В первом примере существует единственный способ выбрать три столицы: города под номерами 2, 3 и 4. Рисунок, соответствующий первому примеру, приведен ниже.

Во втором примере существует четыре варианта выбора трёх столиц из четверки городов: 2, 3, 4 и 5. Можно также выбрать столицами города с номерами 1, 6 и 7. Рисунок, соответствующий второму примеру, приведен ниже.

Система оценивания

Правильные решения для тестов, в которых 3 ≤ n ≤ 50, будут оцениваться из 20 баллов.

Правильные решения для тестов, в которых 3 ≤ n ≤ 500, будут оцениваться из 40 баллов.

Правильные решения для тестов, в которых 3 ≤ n ≤ 5000, будут оцениваться из 60 баллов.

Примеры
Входные данные
4 2
1 2
1 3
1 4
Выходные данные
1
Входные данные
7 2
1 2
1 3
1 4
5 1
5 6
5 7
Выходные данные
5
#111636
Древние династии
  

История Татаро-монгольского ханства богата на правителей. Каждый из N правителей принадлежал к одной из двух династий, причём власть часто переходила от одной династии к другой. Каждое восхождение правителя на престол отмечалось праздником, проводимым 26 марта. В летописях зафиксированы годы проведения этих праздников, причем известно, что правители первой династии устраивали для народа праздник кумыса, а второй — праздник мёда.

На конференции по истории Татаро-монгольского ханства каждый из S учёных предложил свою версию толкования летописи. А именно, i-й историк утверждал, что от каждого праздника кумыса до следующего праздника кумыса проходило не менее KLi лет, но не более KRi лет, в то время как от каждого праздника мёда до следующего праздника мёда проходило не менее MLi лет, но не более MRi лет.

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

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

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

В первой строке входного файла записано число N (2 ≤ N ≤ 200 000) — количество праздников в летописи. Следующая строка содержит целые числа X1, X2, ..., XN (1 ≤ X1 ≤ X2 ≤ ... ≤ XN ≤ 109) — годы проведения праздников.

В третьей строке записано число учёных S (1 ≤ S ≤ 50). В каждой из последующих S строк записаны четыре натуральных числа KLi, KRi, MLi, MRi (1 ≤ KLi ≤ KRi ≤ 109), (1 ≤ MLi ≤ MRi ≤ 109).

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

Первая строка выходного файла должна содержать числа P и Q, где P — номер учёного, версии которого соответствует распределение с наименьшим показателем сомнительности, а Q — показатель сомнительности этого распределения.

Вторая строка должна состоять из N цифр 1 и 2, записанных без пробелов, означающих приход к власти представителя первой или второй династии соответственно. Если существует несколько решений с наименьшим показателем сомнительности Q, выведите любое из них.

В случае, если ни в одной из версий учёных не существует способа распределения периодов правления между династиями так, чтобы не нарушались ограничения на промежутки времени между праздниками, выходной файл должен содержать единственное число 0.

Примечание

Данная задача содержит шесть подзадач. Для оценки каждой подзадачи используется своя группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.

  1. Тесты из условия. Подзадача оценивается в 0 баллов.

  2. 2 ≤ N ≤ 15, 1 ≤ S ≤ 10. Подзадача оценивается в 20 баллов.

  3. 2 ≤ N ≤ 2000, 1 ≤ S ≤ 50, N × S ≤ 2000. Подзадача оценивается в 20 баллов.

  4. 2 ≤ N ≤ 10 000, 1 ≤ S ≤ 50, N × S ≤ 10 000. Подзадача оценивается в 20 баллов.

  5. 2 ≤ N ≤ 200 000, 1 ≤ S ≤ 50, N × S ≤ 200 000. Подзадача оценивается в 20 баллов.

  6. 2 ≤ N ≤ 200 000, 1 ≤ S ≤ 50. Подзадача оценивается в 20 баллов.

Примеры
Входные данные
3
1 2 3
1
1 1 1 1
Выходные данные
1 1
211
Входные данные
4
1 6 9 13
2
1 2 2 3
6 7 3 3
Выходные данные
0
Входные данные
5
3 6 8 9 10
2
2 3 1 1
1 4 1 10
Выходные данные
2 0
21212
#111992
Олимпийский огонь — 2
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

В одном известном всем городе скоро стартуют Зимние Олимпийские игры. В связи с этим организаторы игр решили провести эстафету Олимпийского огня — самую продолжительную и масштабную в истории Олимпийских игр. Эстафета состоит из N этапов, каждый длиной ai километров (1 ≤ i ≤ N). У организаторов имеется бесконечное количество олимпийских факелов, каждый из которых может непрерывно гореть на протяжении K километров забега. По правилам эстафеты каждый факел используется только один раз. В начале каждого этапа участникам эстафеты выдаётся некоторое число факелов, такое, чтобы олимпийский огонь удалось донести до конца этапа. По окончании этапа все использованные (полностью или частично) факелы передаются в дар своим факелоносцам.

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

Напишите программу, которая по известной схеме эстафеты Олимпийского огня определяет, какое максимальное число факелов можно «сэкономить» и какие этапы для этого нужно объединить.

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

В первой строке заданы 3 натуральных числа N, M и K (N ≤ 106, M ≤ 10, K ≤ 108).

Во второй строке заданы N натуральных чисел ai (ai ≤ 109).

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

В первой строке выведите одно натуральное число F — на сколько можно максимально сократить количество используемых факелов на протяжении всей эстафеты.

Во второй строке выведите одно натуральное число P — количество групп объединённых этапов.

Затем в P строках выведите сами группы — по 2 натуральных числа si и ci, где si — номер первого этапа в группе, а ci — количество этапов в группе. Все si должны идти в порядке возрастания, а ci не превосходить M. Если существует несколько оптимальных решений, разрешается вывести любое.

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

Входные данные
5 3 3
1 1 1 3 3
Выходные данные
2
1
1 3
Входные данные
6 3 3
1 1 1 1 1 1
Выходные данные
4
2
1 3
4 3
Входные данные
5 5 2
2 4 6 8 10
Выходные данные
0
0

#113547
Путешествие в Метрополис
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
512 megabytes

Путешествие по стране никогда не бывает простым, особенно когда не существует прямого сообщения между городами. Группа туристов хочет добраться в город Метрополис, используя сеть железных дорог, которая соединяет n городов, пронумерованных от 1 до n. Город, из которого выезжает группа, имеет номер 1, Метрополис имеет номер n.

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

По пути в Метрополис группа может садиться на поезд и сходить с поезда в любом городе маршрута, не обязательно в начальном или конечном. При этом, можно сойти с поезда маршрута i, пересесть на поезд маршрута j, возможно сделать еще несколько пересадок, а потом вновь сесть в поезд того же маршрута i.

Туристы предъявляют высокие требования к выбору способа проезда в Метрополис.

Во-первых, суммарное время, проведенное в поездах, должно быть минимальным.

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

Время, проведенное вне поездов, не учитывается.

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

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

В первой строке входных данных заданы два целых числа (2 ≤ n ≤ 106, 1 ≤ m ≤ 106) — количество городов и количество маршрутов соответственно.

Далее в m строках содержится описание маршрутов.

Описание каждого маршрута начинается с целого числа si  — количество перегонов в маршруте с номером i (1 ≤ si ≤ 106). Далее следуют (2si + 1) целых чисел, описывающих города маршрута и время проезда перегона между соседними городами маршрута, в следующем порядке: vi, 1, ti, 1, vi, 2, ti, 2, vi, 3, ..., ti, si, vi, si + 1, где vi, j — номер j-го города маршрута, ti, j — время проезда перегона между j-м и (j + 1)-м городом (1 ≤ vi, j ≤ n, 1 ≤ ti, j ≤ 1000).

Гарантируется, что s1 + s2 + ... + sm ≤ 106. Никакие два города в описании маршрута не совпадают. Гарантируется, что с помощью имеющихся маршрутов можно добраться из города с номером 1 в город с номером n.

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

Выходные данные должны содержать два целых числа — минимальное суммарное время, которое придется провести в поездах, и максимальное качество пути с таким временем.

Примечание

В первом примере группа туристов отправится прямым маршрутом в Метрополис.

Во втором примере не оптимально проехать напрямую по первому маршруту, так как время в поезде при этом не будет минимальным возможным. Поэтому они отправятся на поезде по маршруту 1 из города 1 в город 2, затем на поезде по маршруту 2 из города 2 в город 3, а затем снова на поезде по маршруту 1 из города 3 в город 5. При этом сумма квадратов промежутков времени, проведенных в поездах между пересадками, равна 32 + 12 + 52 = 35.

В третьем примере добраться из города 1 в город 4 за минимальное время можно, пересаживаясь с маршрута 1 на маршрут 2 в любом из городов 2, 3 или 4. Максимальное качество путешествия достигается при пересадке в городе 2: 12 + 92 = 82.

Обратите внимание, что второй и третий примеры не удовлетворяют ограничениям первой и второй подзадачи, решение будет протестировано на этих подзадачах, если оно пройдет первый тест из примера. Все тесты из примера подходят под ограничения подзадач 3 – 7, решение будет проверяться на тестах этих подзадач только в случае прохождения всех тестов из примера.

Примеры
Входные данные
2 1
1 1 3 2
Выходные данные
3 9
Входные данные
5 2
4 1 3 2 3 3 5 5 10 4
3 4 2 2 1 3 4 1
Выходные данные
9 35
Входные данные
5 2
3 1 1 2 2 3 3 4
3 2 2 3 3 4 4 5
Выходные данные
10 82
#113549
Серверы на Меркурии
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
512 megabytes

Компьютерная система управления станциями на Меркурии состоит из n серверов, пронумерованных от 1 до n. Серверы соединены (n - 1) двусторонними каналами связи, i-й из которых соединяет i-й и (i + 1)-й серверы.

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

Из-за высокой солнечной радиации на Меркурии передавать пакет обновления по каналам связи можно только в некоторые промежутки времени. Для i-го канала связи известен промежуток времени [li, ri], во время которого возможна передача пакета по этому каналу. Пакет передаётся по любому каналу связи мгновенно.

Пакет обновления, переданный на j-й сервер, немедленно устанавливается и помещается в специальный буфер памяти, из которого он может быть передан на другие серверы. Пакет находится в буфере памяти j-го сервера в течение tj секунд с момента его получения. Если в момент нахождения пакета в буфере памяти сервера появляется возможность передать его по каналу связи на соседний сервер, на котором пакет обновления пока не установлен, то он немедленно передаётся по этому каналу связи.

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

Требуется написать программу, которая для всех i от 1 до n определяет, возможно ли установить пакет обновления на все серверы, передав его с Земли на i-й сервер. Если это возможно, то необходимо определить, в какой минимальный неотрицательный момент времени можно установить пакет на этот сервер, чтобы в результате обновление оказалось установлено на всех серверах.

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

Первая строка входных данных содержит n — количество серверов (1 ≤ n ≤ 200 000).

Вторая строка содержит n целых чисел t1, t2, ..., tn, где tj — время нахождения пакета в буфере памяти j-го сервера (0 ≤ tj ≤ 109).

Следующие (n - 1) строк описывают каналы связи. Для описания i-го канала задаются два целых числа li и ri — границы промежутка времени, на протяжении которого возможна передача пакета по этому каналу (0 ≤ li ≤ ri ≤ 109).

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

Выходные данные должны содержать n целых чисел a1, a2, ..., an.

Число ai должно быть равно такому минимальному неотрицательному моменту времени, что при установке пакета обновления на i-й сервер в момент ai, пакет будет в итоге установлен на всех серверах. Если такого момента времени для i-го сервера не существует, необходимо вывести ai =  - 1.

Примечание

В первом примере имеется всего один сервер, минимальное подходящее время, в которое можно установить на него обновление — 0.

Во втором примере есть два сервера, передать обновление между которыми можно в промежуток от 6 до 8. Первый сервер хранит обновление в буфере 3 единицы времени, а второй — 5 единиц времени. Если отправить обновление первому серверу в момент 3, то он передаст его второму серверу в момент 6. Аналогично если отправить обновление второму серверу в момент 1, то он передаст его первому серверу в момент 6.

В третьем примере нельзя передать обновление первому серверу так, чтобы оно передалось третьему серверу, так как канал 2–3 закрывается до того, как открывается канал 1–2. Можно отправить обновление второму или третьему серверу в момент 5. В этот момент канал 2–3 открыт, поэтому его сразу получат второй и третий серверы. В момент 7, когда откроется канал 1–2 обновление ещё будет находиться в буфере второго сервера, и передастся первому серверу.

В четвёртом примере второй сервер хранит пакет 0 единиц времени, а канал 2–3 открыт в промежуток 5–5. Чтобы передать обновление через второй сервер к третьему серверу, оно должно попасть ко второму серверу в момент 5. Если же мы хотим отправить обновление третьему серверу, то это можно сделать в момент 4, при этом оно будет храниться до момента 7 и будет в итоге установлено на все серверы.

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