Вам нужно напечатать \(N\) слов на Movable Type Printer. Movable Type Printers — это старые принтеры, для работы которых требуется ставить маленькие металлические кусочки (каждый из кусочков содержит одну букву) в определенном порядке, образуя таким образом слова. Потом все они вдавливаются в лист бумаги. Таким образом печатается одно слово. Ваш принтер позволяет делать следующие операции:
Изначально на принтере содержится пустое слово. В конце печати на принтере можно оставить непустое слово. Слова, которые вам даны, вы можете печатать в произвольном порядке.
Каждая из трёх операций занимает одну единицу времени. Вам нужно найти последовательность операций, которая печатает данные \(N\) слов за минимальное время. Если минимальных последовательностaей несколько, выведите любую.
Ваша программа должна считать следующие входные данные:
Ваша программа должна вывести следующие данные:
3 print the poem
20 t h e P - - - p o e m P - - - r i n t P
Вы гуляете в парке, где есть \(N\) островов. Когда-то с каждого острова \(i\) перекинули по одному мосту длиной \(L_i\). Всего мостов в парке \(N\). Несмотря на то, что мосты строились по направлению от одного острова к другому, сейчас по ним можно ходить в любом направлении. Также между каждой парой островов ходит паром.
Гулять вам нравится больше, чем кататься на паромах, поэтому вы решили максимизировать суммарную длину мостов, по которым вы пройдёте, соблюдая следующие ограничения:
Заметьте, что необязательно посещать все острова и может оказаться невозможно пройти все мосты.
Даны описания мостов. Найдите максимальное расстояние, которое можно пройти по указанным правилам.
Первая строка ввода содержит единственное целое число \(N\) — количество островов в парке (\(2 \le N \le 1\,000\,000\)). Острова нумеруются целыми числами от \(1\) до \(N\).
Каждая из следующих \(N\) строк описывает мост. \(i\)-я строка описывает мост, ведущий с острова \(i\) двумя целыми числами: первое из них задаёт номер острова, с которым мост соединяет \(i\)-й остров, второе — длину \(L_i\) этого моста. Длина — натуральное число, не превышающее \(100\,000\,000\).
Выведите одну строку, содержащую единственное целое число — максимальное возможное расстояние, которое можно пройти по мостам.
\(N = 7\) мостов в примере таковы: \((1-3)\), \((2-7)\), \((3-4)\), \((4-1)\), \((5-1)\), \((6-3)\) и \((7-2)\). Заметьте, что два различных моста соединяют острова 2 и 7.
Один из способов получить максимальное расстояние таков:
В конце вы окажетесь на острове 2, и суммарное расстояние будет равно \(9+8+4+3 = 24\). Единственный остров, оставшийся непосещённым, — 4. Заметьте, что по окончании описанного путешествия ни один остров больше посетить нельзя. Более точно:
7 3 8 7 2 4 2 1 4 1 9 3 4 2 3
24
Как рассказывала Шахерезада, в одной далёкой стране, посреди пустыни, есть озеро. Вначале в том озере было \(F\) рыбок. Были выбраны \(K\) ценнейших видов драгоценных камней, и каждая рыбка проглотила один камень. Заметьте, что \(K\) может быть меньше \(F\), поэтому некоторым рыбкам достались камни одного вида.
Время шло, рыбки охотились друг на друга. Одна рыбка может съесть другую, если та хотя бы в два раза короче (рыбка \(A\) может съесть рыбку \(B\) тогда и только тогда, когда \(L_A \ge 2L_B\)). Рыбки выбирают своих жертв без каких-то особых правил. Одна рыбка может выбрать несколько меньших рыбок и съесть их одну за одной, а может и не съесть ни одной, даже если способна. Когда рыбка съедает другую, её длина не меняется, однако все камни из живота меньшей рыбки оказываются в животе большей.
Шахерезада рассказывала, что тот, кто сумеет отыскать озеро, получит право поймать одну рыбку оттуда и забрать все камни, оказавшиеся у неё в животе. Вы решили испытать удачу, но перед тем, как отправиться в путь, заинтересовались тем, сколько различных комбинаций камней можно получить, поймав одну рыбку.
Известно, камень какого вида проглотила каждая рыбка вначале. Вычислите количество комбинаций камней, которые можно получить, поймав ровно одну рыбку, по модулю \(M\). Комбинация однозначно определяется количеством камней каждого вида. Любые два камня одного вида неразличимы, порядок камней не имеет значения.
В первой строке записано единственное целое число \(F\) — начальное количество рыбок в озере (\(1 \le F \le 500\,000\)). Во второй строке записано единственное целое число \(K\) (\(1 \le K \le F\)) — количество видов драгоценных камней (пронумерованных целыми числами от \(1\) до \(K\)). В третьей строке записано единственное целое число \(M\) — модуль (\(2 \le M \le 30\,000\)). Каждая из следующих \(F\) строк содержит по два целых числа — длину соответствующей рыбки \(L_x\) и номер вида драгоценного камня \(G_x\), проглоченного ей (\(1 \le L_x \le 1\,000\,000\,000\), \(1 \le G_x \le K\)).
Гарантируется, что хотя бы один камень каждого вида от \(1\) до \(K\) проглочен хотя бы одной рыбкой.
Выведите единственное число — количество возможных комбинаций камней, взятое по модулю \(M\).
Всего 11 возможных комбинаций, поэтому нужно вывести 11 по модулю 7, то есть 4.
Возможные комбинации: \([1]\), \([1,2]\), \([1,2,3]\), \([1,2,3,3]\), \([1,3]\), \([1,3,3]\), \([2]\), \([2,3]\), \([2,3,3]\), \([3]\), и \([3,3]\). (Для каждой комбинации перечислены камни, её составляющие. К примеру, \([2,3,3]\) — комбинация, состоящая из одного камня вида 2 и двух камней вида 3.)
Эти комбинации можно получить следующими способами:
5 3 7 2 2 5 1 8 3 4 1 2 3
4
Ограничения
\(1 \le N \le 1000000\)Входные данные
Ваша программа должна читать из стандартного ввода данные в следующем формате:Выходные данные
Ваша программа должна вывести в стандартный вывод единственную строку, содержащую одно целое число от 0 до \(M-1\) включительно – номер, присвоенный саду, описанному в стандартном вводе, вычисленный по модулю M.
Оценивание
Для некоторых тестов, в сумме оцениваемых в 40 баллов, \(N\) не будет превышать 40.
Примечание к первому примеру
Фактический номер, присвоенный PLPPL, это 12. Ответ равен 5, то есть, 12 по модулю 7.
5 7 PLPPL
5
12 10000 LPLLPLPPLPLL
39
Вас просят найти наибольшее подходящее пространство для постройки новой пирамиды. Вам предоставлена информация о доступной для застройки земли в виде квадратной сетки размера N на M. Основание пирамиды должно быть квадратом со сторонами, параллельными линиям этой сетки и с вершинами, лежащими в узлах этой сетки.
Исследование обнаружило множество из P возможно пересекающихся препятствий, каждое из которых описано прямоугольником на сетке. Для того, чтобы построить пирамиду, все клетки, содержащиеся в квадрате её основания, должны быть расчищены от препятствий. Удаление i-го препятствия стоит Ci, препятствия удаляются целиком. Удаление препятствия не оказывает влияния на другие препятствия, даже пересекающиеся.
Напишите программу, которая по описанию земли для застройки, описанию препятствий и стоимости их удаления и по количеству денег B, которое можно потратить на удаление препятствий, определяет максимально возможную длину стороны основания пирамиды, которую можно построить после очистки земли.
Ограничения
Тесты к этой задаче разбиты на три группы. Для всех групп тестов выполняются следующие ограничения:
Размеры сетки: 1 <= M, N <= 1,000,000 Стоимости удаления препятствий: 1 <= Ci <= 7,000 X-координаты самых левых и самых правых клеток препятствий: 1 <= Xi,1 <= Xi,2 <= M Y-координаты самых верхних и самых нижний клеток препятствий: 1 <= Yi,1 <= Yi,2 <= N1 группа (35 баллов)
Количество денег: B = 0 Количество препятствий: 1 <= P <= 1,0002 группа (35 баллов)
Количество денег: 0 < B < 2,000,000,000 Количество препятствий: 1 <= P <= 30,0003 группа (30 баллов)
Количество денег: B = 0 Количество препятствий: 1 <= P <= 400,000
Формат входных данных
В первой строке два числа -- M и N соответственно.
Во второй строке одно число B.
В третьей строке одно число P.
Каждая из следующих P строк содержит в себе описание очередного препятствия -- пять чисел Xi,1, Yi,1, Xi,2, Yi,2, и Ci.
Формат выходных данных
Выведите одно число - максимально возможную длину стороны основания пирамиды. Если никакую пирамиду построить невозможно, то выведите число 0.
6 9 42 5 4 1 6 3 12 3 6 5 6 9 1 3 3 8 24 3 8 6 9 21 5 1 6 2 20
4
13 5 0 8 8 4 10 4 1 4 3 4 4 1 10 2 12 2 2 8 2 8 4 3 2 4 6 4 5 10 3 10 4 8 12 3 12 4 13 2 2 4 2 21
3