Группа Pink Floyd собирается дать новый концертный тур по всему миру. По предыдущему опыту группа знает, что солист Роджер Уотерс постоянно нервничает при перелетах. На некоторых маршрутах он теряет вес от волнения, а на других - много ест и набирает вес.
Известно, что чем больше весит Роджер, тем лучше выступает группа, поэтому требуется спланировать перелеты так, чтобы вес Роджера на каждом концерте был максимально возможным. Группа должна посещать города в том же порядке, в котором она дает концерты. При этом между концертами группа может посещать промежуточные города.
Первая строка входного файла содержит три натуральных числа n, m и k - количество городов в мире, количество рейсов и количество концертов, которые должна дать группа соответственно (n≤100, m≤104, 2≤k≤104). Города пронумерованы числами от 1 до n. Следующие m строк содержат описание рейсов, по одному на строке. Рейс номер i описывается тремя числами bi, ei и wi - номер начального и конечного города рейса и предполагаемое изменение веса Роджера в миллиграммах (1≤bi,ei≤n, −105≤wi≤105). Последняя строка содержит числа a1, a2, ..., ak - номера городов, в которых проводятся концерты. В начале концертного тура группа находится в городе a1.Гарантируется, что группа может дать все концерты.
Первая строка выходного файла должна содержать число s - количество рейсов, которые должна сделать группа. Вторая строка должна содержать s чисел - номера используемых рейсов. Не существует такой последовательности маршрутов между концертами, что Роджер будет набирать вес неограниченно.
4 8 5 1 2 -2 2 3 3 3 4 -5 4 1 3 1 3 2 3 1 -2 3 2 -3 2 4 -10 1 3 1 2 4
6 5 6 5 7 2 3
На улице уже неделю лил беспросветный дождь, а Игорь все сидел дома и играл в свои любимые игрушки. Но играть так долго в одно и то же ему быстро надоело, и он пошел к родителям выпрашивать новые. Родители быстро сдались, поэтому на следующий день вся семья собралась, и они поехали в магазин игрушек.
При входе в магазин у Игоря сразу разбежались глаза. Ему хотелось и гоночную машинку, и кораблик с белыми парусами, и саблю, которая так и манила его своим блестящим лезвием. Всего в магазине продается \(N\) новых игрушек, причем так получилось, что все они плоские и имеют форму выпуклых многоугольников (действительно, на что еще можно было надеяться в магазине «Сто тысяч и один выпуклый многоугольник для детей младшего школьного возраста»?). Но строгий отец сказал, что купит Игорю только две игрушки. Игорь сразу же начал перебирать в голове варианты, но их оказалось слишком много, а если быть более конкретным, то его интересовало ровно \(Q\) вариантов выбора пары игрушек.
Любознательный Игорь сразу же задумался о тонкостях упаковки игрушек. А именно, для каждой интересующей его пары игрушек \(i\), \(j\) он хочет проделать следующие операции.
Изначально каждая игрушка лежит в своей плоской прямоугольной коробке, которая плотно прилегает к игрушке. Далее Игорь ставит эти две коробки на стол рядом друг с другом (\(i\)-ю игрушку можно поставить как левее \(j\)-й, так и правее), убирает коробки, потом придвигает игрушки друг к другу, насколько это возможно, и кладет то, что получилось, обратно в коробку (обратите внимание на рисунок). Так как Игорь очень экономный, ему нужно знать размеры получившейся коробки. Повлиять на высоту итоговой коробки, двигая игрушки параллельно плоскости стола, нельзя, так что вам нужно помочь Игорю лишь с определением минимально возможной ширины получившейся коробки.
Обратите внимание, что игрушки можно лишь двигать параллельно плоскости стола, поворачивать их каким-либо образом запрещено. Таким образом, задачу можно считать двумерной: ось \(O_x\) совпадает с плоскостью стола, а ось \(O_y\), по которой измеряется высота игрушек и коробок, перпендикулярна плоскости стола. Стороны коробок параллельны соответствующим осям координат. Диковинных игрушек в магазине предостаточно, так что они могут «стоять» на столе, в том числе и балансируя на одной вершине самым непостижимым образом.
Для лучшего понимания условия ознакомьтесь с примером и иллюстрациями к нему.
В первой строке содержится натуральное число \(N\) (1 ≤ \(N\) ≤ 100 000) - количество игрушек. Далее следуют описания \(N\) выпуклых многоугольников в следующем формате: сначала идет натуральное число \(k_m\) (3 ≤ \(k_m\) ≤ 300 000) - количество вершин в \(m\)-м многоугольнике, затем идут \(k_m\) строк, в которых записаны пары целых чисел xm,s, ym,s, по модулю не превосходящих \(10^9\) - координаты вершин \(m\)-го многоугольника в порядке обхода против часовой стрелки, заданные в системе координат соответствующей ему коробки, которая стоит на столе (это означает, что ym,s >= 0, а также для всех игрушек существует вершина \(v_m\), у которой ym,\(v_m\) = 0). Сумма всех \(k_m\) (обозначим ее за \(S\)) не превосходит 300 000.
В следующей строке записано натуральное число \(Q\) (1 ≤ \(Q\) ≤ 500 000) - число вариантов. Следующие \(Q\) строк содержат пары натуральных чисел \(i_t\), \(j_t\) (1 ≤ \(i_t\) < \(j_t\) ≤ \(N\)) - номера сдвигаемых игрушек в очередном варианте.
Выведите \(Q\) строк: для каждого варианта выбора пары одно вещественное число - необходимую ширину коробки. Ответ будет считаться правильным, если все числа посчитаны с абсолютной или относительной погрешностью не более \(10^{-9}\).
Верхний рисунок иллюстрирует исходное размещение игрушек в коробках, а нижние — варианты итогового расположения игрушек (оптимальный вариант слева).
Тесты к этой задаче состоят из четырех групп.
0. Тест 1. Тест из условия, оценивается в ноль баллов.
1. Тесты 2–20. В тестах этой группы \(k_m\) ≤ 100, \(Q\) ≤ 1 000, \(S\) ≤ 10 000. Эта группа оценивается в 25 баллов. Баллы начисляются только при прохождении всех тестов группы.
2. Тесты 21–40. В тестах этой группы \(k_m\) ≤ 300, \(Q\) ≤ 50 000, \(S\) ≤ 100 000. Эта группа оценивается в 25 баллов. Баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае про- хождения всех тестов из первой группы.
3. Тесты 41–65. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 50 баллов. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой и второй групп. Тесты в этой группе оцениваются независимо.
2 5 0 0 4 2 6 6 3 8 -2 4 5 0 0 2 0 8 4 5 11 3 12 1 1 2
14.5000000000
2 3 0 0 0 3 -1 1 3 0 0 1 0 -20 20 1 1 2
21.0000000000
НЛО приземлилось в районе реки, ее вид заворожил инопланетян, потому что на их планете вообще нет рек. Сейчас они хотят построить свой инопланетный поселок на одной из земных рек, но также они знают, что на Земле очень хрупкая экосистема, поэтому нельзя перегораживать реку очень сильно. Но инопланетяне абсолютно не знают, как устроены реки, поэтому они обратились к вам с просьбой написать программу, которая вычислит максимальную пропускную способность реки, после постройки их инопланетного поселка.
Инопланетяне предпочитают строить здания на тех реках, берега которых представляют из себя параллельные прямые, поэтому область реки, где будут строить инопланетяне, можно себе представить как прямоугольную таблицу W × H , у которой каждая клеточка имеет координаты ( X , Y ). Каждая клеточка пропускает через себя 1 кубический метр воды в секунду, и вода может перетекать только между клеточками соседним по стороне. Каждая клеточка на южной стороне реки ( Y = 0 ) имеет приток воды из реки в размере 1 кубический метр воды в секунду. Каждый дом в поселке занимает прямоугольник, состоящий из единичных клеточек; если в клеточке стоит дом, то вода через нее протекать не может. Ваша задача — вычислить, сколько кубических метров за секунду пропускает поселок инопланетян. То есть сколько кубических метров воды вытекает из всех северных клеток поселка ( Y = H - 1 ) в сумме.
Как известно, вода несжимаема, то есть не может накапливаться в клетке, соответственно если в клетку втекло сколько-то воды, то столько же должно и вытечь.
В первой строке содержатся два целых числа W и H — ширина и высота реки соответственно (\(3\leq W \leq 1000;\; 3\leq H \leq 10^{8})\). В следующей строке находится число B — количество домов в поселке инопланетян (\(0 \leq B \leq 1000\)).
Следующие B строк содержат четыре целых координаты X 0 , Y 0 , X 1 , Y 1 . Где X 0 и Y 0 — координаты нижней левой клеточки дома, а X 1 и Y 1 — координаты верхней правой клеточки дома ( 0 ≤ X 0 ≤ X 1 < W и 0 ≤ Y 0 ≤ Y 1 < H ). Домики не перекрываются, но могут касаться по стороне или ребрам.
Выведите одно число — максимальную пропускную способность поселка в кубических метрах в секунду.
3 3 2 2 0 2 0 0 2 0 2
1
5 6 4 1 0 1 0 3 1 3 3 0 2 1 3 1 5 2 5
2
Вася открыл для себя классическую игру «Bomberman», действующий лицом которой является Бомбермен. Этот персонаж передвигается по игровому полю, представляющему собой прямоугольник из N строк и M столбцов. Каждая клетка поля либо свободна для прохода, либо занята стеной. В одной из клеток находится бонус, к которому необходимо добраться Бомбермену. Для этого у него есть ровно 3 бомбы. За ход Бомбермен может сдвинуться в соседнюю клетку, если она свободна, или взорвать стену, расположенную в ней, использовав одну бомбу.
В последнем случае клетка становится проходимой и впоследствии Бомбермен может на нее встать. Вася хочет определить, за какое минимальное количество ходов Бомбермен сможет добраться до бонуса, или же узнать, что это сделать невозможно, тогда Вася может спокойно удалить «Bomberman» - а и вернуться к старой доброй Дотке.Соседними являются клетки, имеющие общую сторону. Бомбермен не может выходить за границы поля.
В первой строке содержатся два числа N и M — количество строк и столбцов поля соответственно ( 1 ≤ N , M ≤ 20 ). Каждая из следующих N строк содержит ровно M символов, описывающих поле. Свободные клетки обозначены символом «.» (ASCII код 46), занятые—символом «W» (ASCII код 87), бонус—символом «*» (ASCII код 42), Бомбермен—символом «B» (ASCII код 66). Гарантируется, что на поле находится ровно один бонус.
Выведите одно число—минимальное количество ходов, необходимое для того, чтобы добраться до бонуса, либо −1, если добраться до бонуса невозможно.
В первом примере необходимо взорвать стену во второй строке в первом столбце и пройти Бомберменом вниз, а затем вправо. Во втором примере необходимо взорвать минимум 4 стены, чтобы добраться до бонуса, поэтому ответ −1.
5 6 B..... WWWWW. ...... .WWWWW .....*
10
9 12 WWWWWWWWWWWW WW...B..WWWW WW.WWWW.WWWW WW.WWWW...WW WW.WWWWWWWWW WWWWWWWWWWWW WWWWWWWWWWWW WWWW*WWWWWWW WWWWWWWWWWWW
-1
Путешествие по стране никогда не бывает простым, особенно когда не существует прямого сообщения между городами. Группа туристов хочет добраться в город Метрополис, используя сеть железных дорог, которая соединяет 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