Год Коровы - 2

Известно, знаки зодиака в Китайском календаре следуют 12-летнему циклу: Ox, Tiger, Rabbit, Dragon, Snake, Horse, Goat, Monkey, Rooster, Dog, Pig, Rat, и затем опять Ox. Менее известен тот факт, что в конце каждого года Ox открывается временной портал, позволяющий коровам переместиться в любой другой год Ox в прошлом или будущем.

Корова Беси хочет посетить N своих предшественников, которые жили много раньше (\(1<=N<=0x10000\)). 0x10000 - это число в 16-ричной системе счисления, что равно 65536 в десятичной.

К несчастью, путешествия во времени утомительны, и Беси предпочитает сделать не более K прыжков во времени (\(1<=K<=N\)). Помогите Беси определить минимальное количество лет, которое потребуется Беси, чтобы посетить всех предшественников и вернуться в текущий год, совершив не более K прыжков во времени по пути.

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

Примеры

Cookie Clicker

В игре Cookie Clicker игрок зарабатывает печеньки (cookies), щёлкая мышкой по изображению большой печеньки. Тратя заработанные печеньки, игрок может покупать различные усовершенствования (ферму, фабрику и т. д.), которые также производят дополнительные печеньки.

Рассмотрим упрощённый вариант этой игры. Пусть игрок может сделать один щелчок мышкой в секунду, что приносит ему одну печеньку. Также в любой момент времени игрок может потратить C печенек на покупку фабрики (при этом у игрока должно быть не меньше C печенек, после покупки фабрики количество его печенек моментально уменьшается на C ). Каждая купленная фабрика увеличивает ежесекундное производство печенек на P штук (то есть если у игрока одна фабрика, то он получает 1  + P печенек в секунду, две фабрики — 1  +  2 P печенек, три фабрики — 1  +  3 P печенек и т. д.). Игрок может приобрести неограниченное число фабрик стоимостью C печенек каждая. Фабрика начинает производить дополнительные печеньки сразу же, например, если после какой-то секунды игры у игрока стало C печенек, то игрок может купить фабрику и уже на следующей секунде его производство печенек увеличится на P штук.

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

Входные данные
Программа получает на вход три целых положительных числа, записанных в отдельных строках: С (стоимость фабрики), P (производительность одной фабрики) и N (необходимое количество печенек).

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

Примеры

Взвешивание камней

Джек нашел N камней и упорядочил их в порядке возрастания их массы. Массы всех камней различны. Самый легкий камень получил номер 1, следующий ≤ 2 и так далее, самый тяжелый получил номер N.

У Джека есть чашечные весы и он решил положить все камни на них в каком-то порядке. Известен порядок, в котором он будет класть камни, и какой камень на какую чашу попадет.

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

Входные данные
Первая строка содержит целое число N (1  N ≤ 100000).

Каждая из следующих N строк содержит по два целых числа: R (1 ≤ R ≤ N) и S (1 ≤ S ≤ 2). R - номер камня, который будет положен на чашу S. Все R будут различны.

Выходные данные
Выведите N строк -  по одной для каждого камня. Если после добавления соответствующего камня чаша 1 тяжелее, выведите “<”. Если сторона 2 тяжелее, выведите “>”. Если невозможно определить, в каком состоянии будут весы, выведите “?”.

Примеры

<
>
>
?
>

Автобусы

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

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

Автобусная сеть страны охватывает N городов, занумерованных целыми числами от 1 до N.

Идеальное расписание содержит M ежедневных рейсов, i-й рейс начинается в городе F_i в момент времени X_i и заканчивается в некотором другом городе G_i в момент времени Y_i. Продолжительность каждого рейса ненулевая и строго меньше 24 часов. Рейс i выполняется одним из автобусов, находящихся в момент времени X_i в городе Fi.

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

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

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

Входные данные
В первой строке задаются целые числа N и М (1 ≤ N, M ≤ 100 000) — количество городов и рейсов автобусов соответственно.

В каждой из следующих M строк содержится описание рейса автобуса: номер города отправления F_i, время отправления X_i, номер города назначения G_i (Fi ≠ Gi), время прибытия Y_i, отделенные друг от друга одним пробелом. Время прибытия и отправления задается в формате HH:MM, где HH — часы от 00 до 23, MM — минуты от 00 до 59.

Выходные данные
Выведите одно число — минимально необходимое количество автобусов. Если расписание невозможно обслуживать в течение неограниченного периода времени конечным числом автобусов, выведите число -1.

Примеры

Эльфы и олени

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

Но волшебные олени – строптивые животные, поэтому не любые два эльфа могут ехать на любом олене. А именно, каждый олень характеризуется некоторой строптивостью a_i, а каждый эльф – темпераментом b_i. Два эльфа j и k могут ехать на i-м олене в том и только в том случае, если либо b_j < a_i < b_k, либо b_k < a_i < b_j.

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

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

Входные данные
В первой строке вводятся два целых числа m и n – количество оленей и эльфов, соответственно ( 1 ≤ m, n ≤ 100 000).

Вторая строка содержит m целых чисел a_i – строптивость оленей ( 0 ≤ a_i ≤ 10⁹). В третьей строке записаны n целых чисел b_i – темперамент эльфов ( 0 ≤ b_i ≤ 10⁹).

Выходные данные
В первой строке  выведите одно число k – максимальное количество оленей, которое Санта-Клаус может включить в свою упряжку. В следующих k строках выведите по три целых числа: d_i, e_i, 1, e_i, 2 – для каждого оленя в упряжке выведите его номер и номера эльфов, которые на нем поедут. Если решений несколько, выведите любое.

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

Примеры

Том Сойер и слово на заборе

Во время покраски забора Том Сойер написал на нем слово s. Однако затем он решил, что слова-палиндромы смотрятся красивее.
Теперь он хочет дописать к имеющемуся слову s справа другое слово g так, чтобы получившееся слово sg было палиндромом. Однако в целях экономии краски длина g должна быть как можно меньше.
Помогите Тому Сойеру определить слово g.

Входные данные:
В первой строке дано слово s (1 <= |s| <= 200000), состоящее из строчных латинских букв.

Выходные данные:
Выведите минимально возможное по длине слово g, которое нужно дописать, чтобы слово sg на заборе стало палиндромом. Если дописывать ничего не надо, то выведите '-'.

Примеры:
 

Мультимножество и XORы

У вас есть q запросов и мультимножество A, изначально содержащее только число 0. Запросы бывают трёх видов:

• + x — добавить в мультимножество A число x.
• - x — удалить одно вхождение числа x из мультимножества A. Гарантируется, что хотя бы одно число x в этот момент присутствует в мультимножестве.
• ? x — вам даётся число x, требуется вычислить максимальное значение побитового исключающего ИЛИ (также известно как XOR) числа x и какого-нибудь числа y из мультимножества A.

Сортировщик Томми

У Томми есть детская игрушка «cортировщик», с расположенными подряд n колышками. На каждом колышке сейчас не более одного диска (то есть на каком-то колышке диск есть, а на каком-то его нет). Томми хочет переложить имеющиеся диски на колышках таким образом, чтобы они образовывали неубывающую последовательность при просмотре слева направо. То есть на каждом следующем колышке количество дисков должно быть не меньше, чем на предыдущем.  Какое минимальное количество дисков Томми необходимо переложить?

Примеры

8
0 0 1 1 1 1 1 1

0

11
1 1 0 0 1 0 0 1 1 1 0

3

Мишины кубики

У маленького Миши есть кубики, на каждом из которых написана одна английская строчная буква. Вчера он выкладывал кубики в два ряда. В первом ряду у Миши n кубиков с буквами, во втором - m кубиков с буквами. Так получилось, что в двух этих рядах нет совпадающих букв. Другими словами, ни одна буква не содержится одновременно в обоих рядах.
Сегодня маленький Миша решил продолжить играть с кубиками. Но теперь он берет один любой кубик из какого-либо ряда и составляет из них третий ряд, добавляя кубик всегда в конец. Маленький Миша никогда не берет более k кубиков подряд из одного и того же ряда. Миша закончил играть тогда, когда у него закончились кубики в каком-то одном ряду (в первом или во втором).
Наблюдавший за игрой папа заметил, что играя таким образом у Миши получилась лексикографически наименьшая строка. По известным двум строкам, которые образуются путем прочтения букв первого и второго ряда и числу k определите строку, которую получил маленький Миша.

Строка x лексикографически меньше строки y только и только тогда, когда выполняется одно из следующих условий:
- x является префиксом y, но x != y;
- в первой позиции, где x и y различаются, в строке x находится буква, которая стоит в алфавите раньше, чем соответствующая буква y.


Входные данные
Программа получает на вход несколько строк. В первой строке записаны три числа: n - количество кубиков в первом ряду, m - количество кубиков во втором ряду, k - целое число(1 <= n, m, k <= 100). Во второй строке записана строка a длиной n - строка, образованная прочтением букв, написанных на кубиках первого ряда. В третьей строке - строка b длиной m - строка, образованная прочтением букв, написанных на кубиках второго ряда.

Выходные данные
Выведите ответ на задачу.
 
 

Примеры

Вечер кёрлинга

Сегодня вечером по телевизору на разных каналах будут показывать n матчей по кёрлингу, причём i-й матч начинается в момент времени l_i и заканчивается в момент времени r_i. 

Василиса хочет посмотреть как можно больше матчей от начала до конца. При этом если какой-то матч заканчивается в момент времени r_i, то она может после него посмотреть любой матч j, который начинается не раньше момента времени r_i, то есть l_j >  r_i (Василиса может моментально переключить каналы в момент окончания матча и начать смотреть новый матч). Также она хочет сделать перерыв длины хотя бы t между какими-то двумя играми, чтобы поужинать, то есть должны найтись два последовательных матча i и j, которые просмотрит Василиса, удовлетворяющие условию l_j - r_i => t. Перерыв не может быть до или после всех просмотренных игр.

Помогите Василисе составить набор, содержащий максимальное количество матчей, которые она сможет просмотреть полностью и при этом сделать перерыв продолжительностью не менее t между какими-то матчами, или определите, что такого набора не существует.

Формат входных данных
Первая строка входных данных содержит число n  (2 ≤ n ≤ 100 000) -  количество показываемых матчей.
Вторая строка входных данных содержит число t (1 ≤ n ≤ 10⁹) -  минимальная длина перерыва, который должна сделать Василиса.
В следующих n строках содержится по два числа l_i  и r_i  ( 1 ≤ l_i < r_i ≤ 10⁹) -  начало и конец i-го матча.

Формат выходных данных
Программа должна вывести число m - максимально возможное количество матчей, которые просмотрит Василиса. Во второй строке выведите m чисел через пробел - номера матчей, которые должна посмотреть Василиса, в порядке просмотра.
Если Василиса не может составить расписание хотя бы из двух матчей так, чтобы между какими-то двумя матчами был перерыв хотя бы t, то выведите число -1.

Замечание
В первом примере ответом будет последовательность матчей 6, 3, 5. Василиса сначала посмотрит матч 6, 
который заканчивается в момент времени 4, потом переключится на матч 3, который продолжается с 4 до 6. 
Затем она сделает перерыв с 6 по 10, после чего просмотрит матч номер 5 с 10 до 12. Получилось расписание из 3 матчей с перерывом, продолжительность которого равна 4. Заметим, что в данном примере правильным ответом также будет последовательность матчей 6, 4, 5, в этом случае продолжительность перерыва между матчами 4 и 5 будет равна 3.

Во втором примере всего два матча, первый заканчивается в 5, а второй начинается в 9, то есть составить расписание, в котором был бы перерыв продолжительностью не менее t=5, нельзя.
 

Fenced In

Стабильные параллели

Решение задач

В этой задаче Вася готовится к олимпиаде. Учитель дал ему \(N\) (\(1 \le N \le 100\)) задач для тренировки. Для каждой из этих задач известно, каким умением \(a_i\) нужно обладать для её решения. Это означает, что если текущее умение Васи больше либо равно заданного умения для задачи, то он может ее решить. Кроме того, после решения \(i\)-й задачи Васино умение увеличивается на число \(b_i\).

Исходное умение Васи равно \(A\). Решать данные учителем задачи он может в произвольном порядке. Какое максимальное количество задач он сможет решить, если выберет самый лучший порядок их решения?

Формат входных данных
Сначала вводятся два целых числа \(N\), \(A\) (\(1 \le N \le 100\), \(0 \le A \le 100\)) — количество задач и исходное умение. Далее идут \(N\) пар целых чисел \(a_i\), \(b_i\) (\(1 \le a_i \le 100\), \(1 \le b_i \le 100\)) — соответственно сколько умения нужно для решения \(i\)-й задачи и сколько умения прибавится после её решения.

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

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

Приключение

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

Глубина ямы равна H. Каждый школьник знает свой рост по плечи h_i и длину своих рук l_i. Таким образом, если он, стоя на дне ямы, поднимет руки, то его ладони окажутся на высоте h_i + l_i от уровня дна ямы. Школьники могут, вставая друг другу на плечи, образовывать вертикальную колонну. При этом любой школьник может встать на плечи любого другого школьника. Если под школьником i стоят школьники j₁, j₂, …, j_k, то он может дотянуться до уровня h_j1 + h_j2 + … + h_jk + h_i + l_i.

Если школьник может дотянуться до края ямы (то есть h_j1 + h_j2 + … + h_jk + h_i + l_i ≥ H), то он может выбраться из нее. Выбравшиеся из ямы школьники не могут помочь оставшимся.

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

Формат входных данных
В первой строке входных данных задается натуральное число N (1 ≤ N ≤ 2000) — количество школьников, попавших в яму.

Далее в N строках содержится по два целых числа: рост i-го школьника по плечи h_i (1 ≤ h_i ≤ 10⁵) и длина его рук l_i (1 ≤ l_i ≤ 10⁵).

В последней строке указано целое число — глубина ямы H (1 ≤ H ≤ 10⁵).

Формат выходных данных
В первой строке выведите K — максимальное количество школьников, которые смогут выбраться из ямы. Если K > 0, то во второй строке в произвольном порядке выведите их номера, разделяя их пробелами. Школьники нумеруются с единицы в том порядке, в котором они заданы во входных данных. Если существует несколько решений, выведите любое.

Счастливые билеты

Оптимизация акции

В сети магазинов <<Мир>> при оплате карточкой Weeza действует акция. При оплате покупки, состоящей не менее чем из \(10\) товаров, плата за самый дешевый товар не берется. Если товаров не меньше 20, то не оплачиваются уже два самых дешевых товара и т.д.

Например, при одновременной покупке \(17\) товаров, покупатель потратит сумму денег равную стоимости только \(16\) самых дорогих из них, а при покупке \(20\) и \(37\) товаров придется заплатить только за \(18\) и \(34\) самых дорогих товара, соответственно.

Миша хочет купить в магазине <<Мир>> \(n\) дисков с альбомами его любимой музыкальной группы. Подобрав подходящие диски, Миша выложил их на ленту в супермаркете в некотором порядке. Так как Миша не только меломан, но и математик, он понял, что ему, возможно, удастся сэкономить, если платить не за все \(n\) товаров одновременно, а разбить их на несколько покупок и оплатить каждую покупку отдельно. Миша решил привлекать к себе как можно меньше внимания и, в частности, не менять порядок товаров на ленте. Таким образом, Миша может только разбивать товары на ленте на группы подряд идущих и платить за каждую группу в отдельности.

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

Формат входных данных
В первой строке находится одно число \(n\) (\(1 \leq n \leq 100\,000\)) — количество дисков на ленте.

Следующая строка содержит \(n\) чисел \(a_i\) (\(1 \leq a_i \leq 10^9\)) — стоимости дисков в порядке расположения на ленте.

Формат выходных данных
Выведите наименьшую возможную стоимость покупки всех дисков с учетом акции при оптимальном разбиении дисков на группы.

В первом примере Мише в любом случае придется оплатить все диски, так как суммарное количество товаров меньше \(10\).

Во втором тестовом примере оптимально во время первой покупки оплатить первые два диска, а за остальные диски заплатить во время второй покупки. Тогда не придется заплатить за диск стоимостью \(9\).

Ударим мостом по бездорожью

Профиль Уральских гор задается ломаной (x₁, y₁), (x₂, y₂), …, (x_N, y_N), для координат вершин которой верны неравенства x₁ < x₂ < … < x_N. Начальные и конечные точки профиля расположены на уровне моря (y₁ = y_N = 0).

На горном профиле заданы две различные точки A и B, между которыми требуется проложить дорогу. Эта дорога будет проходить по склонам гор и проектируемому горизонтальному мосту, длина которого не должна превышать L. Оба конца моста находятся на горном профиле. Дорога заходит на мост с одного конца и выходит с другого. Мост не может содержать точек, расположенных строго под ломаной (строительство тоннелей не предполагается).
Возможные примеры расположения моста                                                                   Невозможное расположение моста


Достоверно известно, что строительство такого моста в данной местности возможно, причем позволит сократить длину дороги из точки A в точку B. Требуется написать программу, которая определит такое расположение горизонтального моста, что длина дороги от точки A до точки B будет наименьшей.

Формат входных данных
Первая строка входных данных содержит два целых числа N и L — количество вершин ломаной (2 ≤ N ≤ 100 000) и максимальную длину моста (1 ≤ L ≤ 10⁶) соответственно. Вторая строка  содержит координаты точки A, третья строка — координаты точки B. Точки A и B различны.

Последующие N строк содержат координаты вершин ломаной (x₁, y₁), (x₂, y₂), …, (x_N, y_N). Координаты вершин ломаной, а также точек A и B, задаются парой целых чисел, не превосходящих по абсолютному значению 106. Гарантируется, что x₁ < x₂ < … < x_N и y₁ = y_N = 0, а также, что точки A и B принадлежат ломаной.

Формат выходных данных
В первой и второй строках выходных данных выведите координаты концов моста с точностью не менее 5 знаков после десятичной точки. В случае, когда решений несколько, выведите любое из них.

Костюмы

Команда ЛКШ по плаванию состоит из N игроков, известна базовая скорость каждого игрока Vi. В шкафчике находится K магических плавательных костюмов, про которые тренер пустил слух, что они дают бонус к скорости. Костюмы бывают двух типов - спецназовские костюмы с шипами дают процентный бонус, а обычные плавки дают количественный бонус. Мощность воздействия костюма описывается целым числом от 1 до 300. Для спецназовских костюмов оно показывает, на сколько процентов увеличится базовая скорость, а для плавок - на какую величину.

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

Входные данные
В первой строке записано число N (0 <= N <= 400) - число спортсменов, далее N чисел, которые описывают их базовые скорости (целое число от 1 до 10000). Далее записано число K (0 <= K <= 800) - количество костюмов, затем K пар целых чисел, описывающих соответствующую костюмы (тип и мощность). Тип пары описывается либо единичкой (спецназовские костюмы), либо двоечкой (плавки).

Выходные данные
Вывести максимальную суммарную скорость команды с точностью до 4-х знаков.

Турнир

В турнире по хоккею участвовало K команд, каждая сыграла с каждой по одному матчу. За победу команда получала 2 очка, за ничью – 1, за поражение – 0 очков.

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

Входные данные
В первой строке входных данных содержится одно натурально число K, не превосходящее 100 – количество команд. Во второй строке  задаются  через пробел K целых неотрицательных чисел, не превосходящих 2(K–1), – количество очков, набранных командами, занявшими первое, второе, …, K-е места соответственно (то есть каждое следующее число не больше предыдущего).

Выходные данные
Выведите турнирную таблицу в следующем формате. Таблица должна состоять из K строк с результатами игр команд, занявших первое, второе, …, последнее место (команды, набравшие одинаковое число очков, могут быть расположены в таблице в любом порядке). В каждой строке должно быть записано K чисел через пробел – количество очков, набранных в игре данной команды с первой, второй, … командами соответственно. Количество очков – это число 0, 1 или 2. В клетках на главной диагонали (соответствующих не существующей игре команды "самой с собой") нужно записать нули.

Гарантируется, что входные данные соответствуют реальному турниру, то есть хотя бы одна таблица, соответствующая входным данным, может быть построена. Если таких таблиц несколько, выведите любую из них.

Мосты

Одна сказочная страна располагалась в дельте далекой реки ( far away river ).

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

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

Входные данные
Первая строка входных данных содержит 4 числа n, k, sh и sc — число городов, число мостов, которым можно построить, скорость лошади и скорость экипажа в метрах в секунду (1 ≤ k < n≤ 10 000, 1 ≤sh; sc·≤ 100 000). Каждая из следующих n – 1 строк содержит три целых числа b_i, e_i — номера соединяемых городов и длину дороги в метрах l_i (1 ≤ l_i ≤ 10⁶). Города пронумерованы от 1 до n, дороги пронумерованы от 1 до n – 1.

Выходные данные
k чисел — номера мостов, которые должны быть построены. Если существует несколько оптимальных планов строительства мостов, то выведите любой из них.

Квадрат

Требуется в каждую клетку квадратной таблицы размером NxN поставить ноль или единицу так, чтобы в любом квадрате размера KxK было ровно S единиц.

Входные данные
Во входных данных записаны три числа — N, K, S (1 ≤ N ≤ 100, 1 ≤ K ≤ N, 0 ≤ S ≤ K²).

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

Кластеры роботов

На производстве расположены \(n\) роботов, пронумерованных от \(1\) до \(n\). Любая пара роботов может быть либо соединена проводом, либо нет. Всего на производстве \(m\) проводов и \(i\)-й из них сейчас соединяет роботов с номерами \(a_i\) и \(b_i\).

Вы находитесь рядом с роботом номер \(1\). Роботом номер \(t\) можно управлять, если он связан с первым некоторой цепочкой проводов, то есть

• либо если \(t = 1\);

• либо если существуют такие \(i_1, \ldots, i_k\), что \(i_1 = 1\), \(i_k = t\), и любые два соседних в этой последовательности робота \(i_j\) и \(i_{j + 1}\) связаны проводом.

Любому из роботов, которыми можно управлять, можно послать команду <<извлеки второй конец подключенного к себе провода и подключи его к другому роботу>>. Иными словами, если роботом номер \(t\) можно управлять, и есть провод, соединяющий его с роботом номер \(x\), то можно заменить провод \((t, x)\) на провод \((t, y)\) для любого \(y \neq t\), еще не связанного проводом с \(t\). Обратите внимание, что после этого вы можете потерять управление над \(t\)-м роботом, если единственная связь \(t\)-го с первым проходила через \(x\)-й.

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

Формат входных данных
В первой строке записано целое число \(T\) (\(1 \le T \le 1000\)) — количество наборов входных данных в тесте.

Первая строка каждого набора входных данных содержит целые числа \(n\) и \(m\) (\(1 \leq n \leq 10^5\); \(0 \leq m \leq 1.5 \cdot 10^5\)) — количество роботов и количество проводов, соответственно.

В следующих \(m\) строках дано описание проводов: в \(i\)-й строке даны целые числа \(a_i\) и \(b_i\) (\(1 \leq a_i, b_i \leq n\); \(a_i \neq b_i\)) — номера роботов, соединенных \(i\)-м проводом. Гарантируется, что никакие два провода не соединяют одну и ту же пару роботов.

Также гарантируется, что сумма \(n\) по всем наборам входных данных не превосходит \(10^5\) и сумма \(m\) по всем наборам входных данных не превосходит \(1.5 \cdot 10^5\).

Формат выходных данных
Для каждого набора входных данных выведите в первой строке через пробел максимальное количество роботов, управление над которыми можно получить, и количество действий \(k\), которое для этого понадобится.

В следующих \(k\) строках выведите сами описания действий по одному на каждой строке. Описание действия должно состоять из трех целых чисел \(t\), \(x\) и \(y\) (\(1 \leq t, x, y \leq n\); \(x \neq y\)), означающих, что робот номер \(t\) меняет провод \((t, x)\) на провод \((t, y)\).

Если возможных ответов несколько, выведите любой. Обратите внимание, что \(k\) при этом обязано быть наименьшим, при котором можно подключить максимальное количество роботов.

65873

Галактическая станция «Вавилон» имеет N (0 < N <= 10) ангаров для космических кораблей.
Цикл предполетной подготовки длится M (0 < M <= 10) суток. Цикл начинается в тот же момент, как корабль залетает в ангар. До окончания цикла корабль не может покинуть ангар и соответственно начать новый рейс.
Сутки на станции составляют 24 часа. Календарь на станции составляет 365 дней, которые не делятся на месяцы.
Вам попали в руки фрагменты станционного журнала (0 < K <= 1000 строк). В нем фиксируются даты и время прибытия кораблей в зону станции, а также заявки на рейсы со станции. Гарантируется, что все страницы относятся к одному году.
Если корабль подлетает к станции, а все ангары заняты, то ему отказывают в обслуживании. Если вылет со станции назначен на тот же час, что и прилет нового корабля, будем считать, что сначала ангар освобождается, а потом новый корабль размещается в пустом ангаре (начало цикла будет считаться с момента прилета).
Если приходит запрос на рейс со станции, то в рейс уходит тот корабль, который готов к вылету. Если таких кораблей несколько, то выбирается тот, который дольше находится на станции. Если готовых к рейсу кораблей нет, то рейс задерживают и ждут, когда появится корабль, который пройдет цикл предполетной подготовки. Если до конца периода кораблей для выполнения рейса не найдется, то заявка считается НЕ задержанной, а отклоненной.
По данным журнала определите скольким кораблям было отказано и сколько рейсов было отклонено в рассматриваемый период.

Входные данные:
В первой строке через пробел три числа N M K.
Дальше K строк в формате
День Час Признак
Где День – это номер дня от начала года; Час – час события; Признак это 1, если корабль прилетает, -1, если это запрос на вылет.
Выходные данные:
Два целых числа, каждое на новой строке:
– количество отказов в обслуживании;
– количество отклоненных заявок.

Примечание
В журнале 9 записей.
1) 1 9 1
2) 8 12 -1
3) 6 15 -1
4) 6 12 -1
5) 2 18 1
6) 5 6 1
7) 6 12 1
8) 7 12 -1
9) 2 21 1
Корабли, прибывшие 1-го в 9:00 и 2-го в 18:00, были поставлены в два ангара, имеющиеся на станции (1-ая и 5-ая строки журнала).
6-го числа в 12:00 1-ый ангар покинул корабль по заявке из 4-ой строки журнала. В тот же момент его место занял корабль с 7-ой строки.
На момент прилета кораблей из 6-ой и 9-ой строк оба ангара были заняты. Эти корабли получили отказ.
Выполнение заявок с 3-ей и 8-ой строк журнала было задержано, так как не было готовых к вылету кораблей.
Заявка со 2-ой строки была отклонена, так как в ангарах и на подлете в рассматриваемый интервал времени кораблей не было.

Книги на полке

Библиотекарь расставляет книги на полке длиной \(W\) сантиметров. У него есть \(n\) книг; \(i\)-я книга имеет размеры \(a_i \times b_i\) сантиметров.

Каждую книгу можно поставить на полку двумя способами: одной стороной к соседней книге (тогда она занимает вдоль полки \(a_i\) сантиметров) или другой стороной (тогда \(b_i\) сантиметров). Способ расстановки выбирается для каждой книги независимо.

Библиотекарь хочет поставить на полку максимально возможное количество книг. Какие именно книги — неважно, лишь бы их число было наибольшим. Суммарная ширина расставленных книг не должна превышать длины полки.

Помогите ему определить это максимальное число книг.

Формат входных данных

В первой строке — два целых числа \(n\) и \(W\) (\(1 \le n \le 2 \cdot 10^5\), \(1 \le W \le 10^{14}\)) — количество книг и длина полки.

В следующих \(n\) строках — по два целых числа \(a_i\) и \(b_i\) (\(1 \le a_i, b_i \le 10^9\)) — размеры \(i\)-й книги.

Формат выходных данных

Одно целое число — максимальное количество книг, которые можно расставить на полке.

Рейтинг участников

Школьник Тимур участвует в серии онлайн-соревнований по программированию. За весь год проходит \(n\) соревнований, и Тимур заранее знает, сколько очков он может набрать в каждом из них: за \(i\)-е соревнование он получит \(s_i\) очков.

По правилам рейтинга, в итоговую сумму идут только \(k\) соревнований по выбору участника (остальные просто не засчитываются). Тимур хочет выбрать такие \(k\) соревнований, чтобы получить максимальную суммарную сумму очков.

Помогите ему вычислить эту максимальную сумму.

Формат входных данных

В первой строке — два целых числа \(n\) и \(k\) (\(1 \le k \le n \le 10^5\)) — общее количество соревнований и сколько из них идут в зачёт.

Во второй строке — \(n\) целых чисел \(s_i\) (\(0 \le s_i \le 10^9\)), разделённых пробелами, — количество очков за каждое соревнование.

Формат выходных данных

Одно целое число — максимальная суммарная сумма очков за \(k\) выбранных соревнований.

Примечание

В первом примере из пяти соревнований с очками \(1, 5, 3, 8, 2\) надо выбрать три. Лучше всего взять соревнования с очками 8, 5 и 3 — в сумме 16.

Во втором примере в зачёт идут все соревнования, так что ответ — сумма всех очков.

Экспедиция на Марс

Центр управления отправляет на Марс грузовую капсулу. Она может поднять не более \(W\) килограммов полезной нагрузки. Учёные отобрали \(n\) научных приборов, которые хотят отправить в этой миссии; масса каждого прибора равна \(w_i\) килограммов.

Каждый прибор можно либо отправить целиком, либо оставить на Земле — разбирать их на части нельзя. Место в капсуле есть: ограничение только по массе. Цель миссии — отправить максимальное количество разных приборов, чтобы провести как можно больше экспериментов (какие именно приборы полетят — неважно, лишь бы число было максимальным).

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

Формат входных данных

В первой строке — два целых числа \(n\) и \(W\) (\(1 \le n \le 10^5\), \(1 \le W \le 10^9\)) — количество приборов и грузоподъёмность капсулы в килограммах.

Во второй строке — \(n\) целых чисел \(w_i\) (\(1 \le w_i \le 10^4\)), разделённых пробелами, — масса каждого прибора в килограммах.

Формат выходных данных

Одно целое число — максимальное количество приборов, которые можно отправить на Марс.

Примечание

В первом примере лучше всего отправить приборы массами \(1 + 2 + 3 + 4 = 10\) кг — ровно помещаются в капсулу, итого 4 прибора. Прибор массой 7 кг остаётся на Земле.

Во втором примере каждый прибор по отдельности весит больше грузоподъёмности капсулы. Ни один прибор отправить нельзя.

Классифайд - 1

Вася открыл собственный классифайд (доску объявлений). Устроен его классифайд следующим образом: для каждого типа товара продавец с номером \(i\) может выставить на продажу только одну единицу товара и заранее указывает минимальную цену \(S_i\), за которую он готов его продать. Каждый покупатель может купить только одну единицу товара, покупатель с номером \(j\) указывает максимальную цену \(B_j\), за которую он готов купить товар. Раз в день Вася собирает все заявки и распределяет покупателей и продавцов, которые заключат сделку и по какой цене. При этом сделка между продавцом \(i\) и покупателем \(j\) может состояться только если \(S_i \le B_j\) по любой цене от \(S_i\) до \(B_j\) (цену назначает Вася).

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

Формат входных данных
В первой строке задается число наборов тестовых данных \(T\). В этой задаче \(T\) всегда равно 1.

В первой строке описания каждого набора записано число \(N\) (\(1 \le N \le 10\)) — количество продавцов.

В следующей строке записано \(N\) чисел \(S_i\) (\(1 \le S_i \le 100\)).

В следующей строке записано число \(M\) (\(1 \le M \le 10\)).

В следующей строке записано \(M\) чисел \(B_i\) (\(1 \le B_i \le 100\)).

Описания наборов отделяются друг от друга пустой строкой.

Формат выходных данных
Для каждого набора входных данных выведите одно число — максимальную суммарную стоимость проданных товаров.

В этой задаче на проверку необходимо сдать исходный код программы.

Why Did the Cow Cross the Road

Коровы Фермера Джона учатся переходить через дорогу эффективно. И ищут цыплят в качестве учителей.

Цыплята очень занятые существа и имеют ограниченное время для помощи коровам. Всего имеется \(C\) цыплят на ферме (\(1 \leq C \leq 20,000\)), последовательно пронумерованных \(1 \ldots C\), и каждый цыплёнок \(i\) может помогать коровам ровно время \(T_i\). Коровы никуда не торопятся. Всего имеется \(N\) коров на ферме (\(1 \leq N \leq 20,000\)), последовательно пронумерованных \(1 \ldots N\), и корова \(j\) способно переходить дорогу между временами \(A_j\) и \(B_j\). В идеале корова \(j\) хочет найти цыплёнка \(i\), который поможет её перейти через дорогу. Для того, чтобы их расписания были совместимы, необходимо чтобы выполнялось неравенство \(A_j \leq T_i \leq B_j\).

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

Circular Barn

Будучи фанатом современной архитектуры, Фермер Джон построил новый амбар в форме круга. Внутри амбар составляет кольцо из \(n\) комнат, пронумерованных по часовой стрелке \(1 \ldots n\) по периметру (\(3 \leq n \leq 1,000\)). Каждая комната имеет двери в две соседние комнаты, а также дверь из амбара во внешний мир.

У ФД есть ровно \(n\) коров, и он хочет поместить по одной корове в каждую комнату. Однако своенравные коровы выстроились не как нужно, и возможно несколько коров собрались у одной внешней двери. А именно, \(c_i\) коров стоит перед дверью с номером \(i\). Разумеется, \(\сумма c_i = n\).

Чтобы коровы добрались до своих мест ФД собирается применить следующий подход: каждая корова входит в дверь, перед которой она стоит и идёт по часовой стрелке в свою комнату. В предположении, что проход коровы через \(d\) дверей отнимает у неё \(d^2\) энергии, определите минимальное количество энергии, которое требуется, чтобы распределить коров по одной в комнату.

Milk Pails

Фермер Джон получил заказ доставить ровно \(M\) единиц молока (\(1 \leq M \leq 1,000\)). К несчастью, его молочная машина сломалась и у него есть три бидона молока целых размеров \(X\), \(Y\), and \(M\) (\(1 \leq X < Y < M\)). Все три бидона изначально пустые. Используя эти три бидона, он может выполнять любое количество операций двух следующих типов:

- Он может заполнить самый маленький бидон (размера \(X\)) полностью до самого верха \(X\) единицами молока, и перелить всё молоко в бидон размера \(M\), если не переполнится бидон с размером \(M\)

- Он может заполнить средний бидон (размера \(Y\)) полностью до верха \(Y\) единицами молока и перелить всё молоко в бидон размера \(M\), если не переполнится бидон с размером \(M\)

ФД понимает, что он не всегда может полностью заполнить бидон с размером \(M\), помогите ему определить максимальное количество молока, которое он может залить в бидон с размером \(M\)

Angry Cows

Беси создала новую игру. Игрок стреляет коровами на одномерную сцену, состоящую из множества стогов сена расположенных в различных точках на числовой прямой. Каждая корова приземляется с силой достаточной, чтобы разрушить ближайшие к точке приземления стоги. Цель - использовать множество коров так, чтобы разрушить все стоги сена.

Имеется \(N\) стогов сена расположенных в целочисленных позициях \(x_1, x_2, \ldots, x_N\) на числовой прямой. Если корова приземляется с энергией \(R\) в позиции \(x\), это вызывает взрыв "радиуса \(R\)", разрушающий все стоги сена в диапазоне \(x-R \ldots x+R\).

Всего имеется \(K\) коров для выстрелов, каждая с одной и той же энергией \(R\). Определите минимальную целую величину \(R\) такую, что возможно используя эти \(K\) коров разрушить все стоги сена на сцене.

High Card Wins

Корова Беси - фанат карточных игр. Однако у неё нет достойных противников. Все они играют в полностью предсказуемой манере. Однако надо ещё придумать, как выиграть у них.

Беси и Эльза играют в простую карточную игру, в которой имеется колода из \(2N\) карт, последовательно пронумерованных \(1 \ldots 2N\). Они делят её поровну - \(N\) карт Беси и \(N\) карт Эльзе. Затем они играют \(N\) раундов, в каждом из которых Беси и Эльза выкладывают по одной карте, и тот, у кого карта больше, зарабатывает очко.

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

High Card Low Card (Gold)

Беси и Эльза играют в простую карточную игру. Берётся колода из \(2N\) карт, последовательно пронумерованных \(1 \ldots 2N\), и делят их поровну - \(N\) карт Беси и \(N\) карт Эльзе. Затем они играют \(N\) раундов, в каждом из которых Беси и Эльза выкладывают по одной карте. В первых \(N/2\) раундах очко зарабатывает тот игрок, у которого карта больше. А в последних \(N/2\) раундах очко выигрывает тот игрок, у которого карта меньше.

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

Cow Jog

N (1 <= N <= 100,000) коров бегут по одной бесконечно длинной дорожке.
Все коровы начинают в различных позициях и некоторые коровы бегут с
разной скоростью.

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

Забег длится T минут (1 <= T <= 1,000,000,000).
Определите, сколько групп образуется к концу забега.
Две коровы рассматриваются принадлежащими к одной группе, если
они окажутся в одной позиции в конце T минут.

Формат входных данных

Первая строка ввода содержит два целых числа N и T.

Каждая из следующих N строк содержит начальную позицию и скорость
одной коровы. Позиция - неотрицательное целое число, а скорость -
положительное целое число. Оба числа не превысят 1 миллиард.
Все коровы начинают в различных позициях, заданных на вводе в порядке
возрастания.

Формат выходных данных

Одно целое число, указывающее сколько групп останется после T минут.

Cow Jog

Имеется N коров, бегающих вдоль бесконечно-длинной прямой
трассы. (1 <= N <= 100,000). Каждая корова начинает
с уникальной позиции и некоторые коровы бегут с различной скоростью.
Трасса имеет только одну дорожку и корова не может
перепрыгнуть другую. Поэтому, когда более быстрая корова
настигает более медленную, она замедляет свою скорость
и становится частью некоторой бегущей группы коров.

Фермер Джон хочет, чтобы ВЫ посчитали,
сколько таких групп образуется.

Формат входных данных

Первая строк ввода содержит целое число N.
Каждая из последующих строк содержит начальную позицию
и скорость одной коровы. Позиция - это неотрицательное
целое число, а скорость - положительное целое число,
оба числа не более 1,000,000,000.
Все коровы начинают в различных позициях, которые
задаются в порядке возрастания на вводе.

Формат выходных данных

Одно целое число, указывающее, сколько групп останется.

Lazy Sort

У Фермера Джона есть \(N\) коров (\(2 \leq N \leq 5\cdot 10^6\)) и пытается заставить их отсортировать неотрицательный целочисленный массив \(A\) длины \(N\), полагаясь на их лень. У него много тяжелых коробок, поэтому он выстраивает коров одну за другой, где корова \(i+1\) находится за коровой \(i\), и дает \(a_i\) коробок корове \(i\) (\(0\le a_i\)).

Коровы по своей природе ленивы, поэтому они всегда ищут способ передать свою работу кому-то другому. От коровы \(1\) до \(N-1\) по порядку каждая корова смотрит на корову позади себя. Если у коровы \(i\) строго больше коробок, чем у коровы \(i+1\), корова \(i\) считает, что это «несправедливо» и отдает одну из своих коробок корове \(i+1\). Этот процесс повторяется, пока каждая корова не будет удовлетворена.

Фермер Джон пометил количество ящиков \(b_i\), которое каждая корова \(i\) держит и создал массив \(B\) из этих величин. Если \(B = sorted(A)\) тогда ФД счастлив. К несчастью. ФД забыл все кроме \(Q\) величин массива \(A\). (\(2 \leq Q \leq \min(N, 100)\)). К счастью, эти величины включают количество ящиков, которое он собирается дать первой и последней корове. Каждое число, которое помнит ФД задано в виде \(c_i \; v_i\), представляющее, что \(a_{c_i}=v_i\). (\(1 \leq c_i \leq N\), \(1\le v_i\le 10^9\)). Определите количество различных способов, которыми могут быть заполнены пропущенные величины так чтобы ФД был счастливым. ответ выводите по модулю \(10^9+7\).

More Cow Photos

Фермер Джон выстроил коров в ряд и хочет их сфотографировать.

Каждая из \(N\) коров \((1 \le N \le 10^5)\) имеет целую высоту от \(1\) до \(N\). ФД хочет сфотографировать их в определённом порядке. Если коровы с высотами \(h_1, \dots, h_K\) стоят в ряд слева направо, он хочет, чтобы для их высот выполнялись следующие три свойства:

• Чтобы высоты коров сначала возрастали, а потом убывали. Формально, должно существовать такое целое число \(i\), что \(h_1 \le \dots \le h_i \ge \dots \ge h_K\).
• Чтобы рядом стояли коровы с одинаковой высотой. Формально, \(h_i \neq h_{i+1}\) для \(1 \le i < K\).
• Чтобы фотография была симметричной. Формально, если \(i + j = K+1\), then \(h_i = h_j\).

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

The Best Lineup

Фермер Джон выстроил \(N\) \((1 \leq N \leq 2 \cdot 10^5)\) своих коров в ряд \(a\). \(i\)'-ая корова от начала ряда \(a\) помечена целым числом \(a_i\) (\(1 \leq a_i \leq N\)). Несколько коров могут быть помечены одним и тем же числом.

ФД конструирует ряд \(b\) следующим образом:

• Изначально массив \(b\) пустой.
• Пока массив \(a\) не пустой, удалить первый элемент ряда \(a\) и добавить или не добавить этот элемент в конец массива \(b\).

ФД хочет сконструировать \(b\) так, чтобы последовательность меток в \(b\) от начала к концу была лексикографически наибольшей.

Прежде чем ФД начнёт конструировать ряд \(b\), он может выполнить следующую операцию не более чем один раз.

• Выбрать корову в ряду \(a\) и переместить её в любую позицию, кроме текущей.

При условии, что ФД оптимально выполняет эту операцию не более одного раза, выведите лексикографически наибольшую последовательность \(b\), которую он сможет получить.

Каждый тест состоит из \(T\) (\(1 \leq T \leq 100\)) независимых подтестов.

Making Mexes

Вам дан массив \(a\) из \(N\) неотрицательных чисел \(a_1, a_2, \dots, a_N\) (\(1\le N\le 2\cdot 10^5, 0\le a_i\le N\)). За одну операцию Вы можете изменить любой элемент \(a\) на любое неотрицательное число.

mex массива это минимальное неотрицательное число, которого нет в массиве. Для каждого \(i\) в интервале от \(0\) до \(N\) включительно, вычислите минимальное количество операций, которое Вы должны сделать, чтобы сделать mex массива \(a\) равным \(i\).

Cowmpetency

Фермер Джон нанимает нового вожака стада для своих коров. Для этого он интервьюирует \(N\) (\(2 \leq N \leq 10^5\)) коров на эту позицию. После интервью \(i\)-го кандидата он назначает целое число "уровень компетенции" \(c_i\) от \(1\) дo \(C\) включительно (\(1 \leq C \leq 10^9\)).

Поскольку ФД интервьюировал много коров, он не помнит все \(c_i\). Однако он помнит \(Q\) (\(1 \leq Q < N\)) пар чисел \((a_j, h_j)\) где корова \(h_j\) компетенция которой была строго больше, чем уровень компетенции коров от \(1\) до \(a_j\) (\(1 \leq a_j < h_j \leq N\)).

ФД говорит Вам последовательность \(c_1, \dots, c_N\) (где \(c_i = 0\) означает, что он забыл уровень компетенции коровы \(i\), и \(Q\) пар \((a_j, h_j)\). Помогите ему определить лексикографически минимальную последовательность уровней компетенции, соответствующую этой информации или указать, что такой последовательности не существует. Последовательность чисел называется лексикографически меньше другой последовательности если в ней меньшее число не первой позиции, где эти последовательности различаются.

Каждый ввод содержит \(T\) \((1 \leq T \leq 20)\) независимых подтестов. Гарантируется, что сумма \(N\) по всем подтестам не превысит \(3 \cdot 10^5\).

Majority Opinion

У Фермера Джона важная задача - решить какой тип сена купить для своих коров.

У Фермера Джона есть \(N\) коров (\(2 \le N \le 10^5\)) пронумерованных от \(1\) до \(N\). Каждая корова любит ровно один тип сена \(h_i\) (\(1 \le h_i \le N\)). ФД хочет, чтобы все его коровы любили один тип сена.

Чтобы это случилось, ФД может сформировать фокус-группы. Фокус-группа состоит из всех коров в непрерывном интервале от \(i\) до \(j\), включительно. Если в фокус-группе более половины коров любит один и тот же некоторый тип сена, то все коровы начинают любить этот тип сена, иначе ни у одной коровы не изменяется любимый тип сена. Например, если фокус группа состоит из 16 коров, 9 или более из которых любят один и тот же тип сена, то и остальные 7 коров теперь будут любить этот же тип сена.

ФД хочет узнать, какие типы сена могут стать любимыми всем коровами. В один момент времени он может создать только одну фокус группу, но он может последовательно создавать сколько угодно фокус-групп, чтобы все коровы полюбили один и тот же тип сена.

Test Tubes

п»ї

Беси занялась химией. В данный момент у неё есть жидкости двух различных цветов \(1\) и \(2\), которые плохо смешиваются одна с другой. У неё также есть две различных колбы бесконечной емкости наполненные \(N\) \((1 \leq N \leq 10^5)\) единицами смесей жидкостей этих двух цветов. Смеси делятся на слои отдельных цветов. Поэтому колбы можно рассматривать как строки \(f_1f_2\ldots f_N\) и \(s_1s_2\ldots s_N\) где \(f_i\) представляет цвет жидкости, которая находится на высоте \(i\) единиц от дна первой колбы, \(s_i\) представляет цвет жидкости, которая находится на высоте \(i\) единиц от дна второй колбы,

Беси хочет разделить эти жидкости так, чтобы каждая колба содержала все единицы жидкости одного цвета. У Беси есть также пустой стакан бесконечной емкости, чтобы помочь ей решить её задачу. Когда Беси делает одно переливание, она переливает всю жидкость цвета \(i\) наверх из одной колбы в другую или в стакан.

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

В каждом тесте будет \(T\) (\(1 \leq T \leq 10\)) подтестов с параметром \(P\) для каждого подтеста.

Предположим, что минимальное количество переливаний, чтобы разделить жидкости по колбам равно \(M\).

• если \(P=1\), Р’С‹ получите баллы, если выведите только \(M\).
• Если \(P=2\), Р’С‹ получите баллы, если выведите целое число \(A\) такое, что \(M \leq A \leq M+5\), Р·Р° которым следует \(A\) строк, которые конструируют это решение Р·Р° \(A\) С…РѕРґРѕРІ. Каждая строка должна содержать описание источника Рё приемника жидкости (\(1\), \(2\), или \(3\) для стакана). Колба-источник должна быть непустой перед переливанием, Рё нельзя переливать РІ себя.
• If \(P=3\), Р’С‹ получите баллы, если выведите \(M\), Р·Р° которым следует правильная конструкция, использующая это количество С…РѕРґРѕРІ.

ПР�МЕР ВВОДА:

6
4 1
1221
2211
4 2
1221
2211
4 3
1221
2211
6 3
222222
111112
4 3
1121
1222
4 2
1121
1222

ПР�МЕР ВЫВОДА:

4
4
1 2
1 3
2 1
3 2
4
1 2
1 3
2 1
3 2
1
2 1
5
2 3
1 2
1 3
1 2
3 1
6
2 3
1 2
1 3
1 2
2 1
3 2

Вот как это делается

1: 1221
2: 2211
3: 

1: 122
2: 22111
3: 

1: 1
2: 22111
3: 22

1: 1111
2: 22
3: 22

1: 1111
2: 2222
3:

В последнем подтесте пминимальное количество переливаний - \(5\). Однако, поскольку \(P=2\), то данная конструкция с \(6\)-ю ходами корректна, посокльку она не более чем на \(5\) переливаний от оптимального ответа.

Автор: Suhas Nagar

Lazy Cow

Беси готовит тесты для олимпиады. Каждую минуту она может выбрать не готовить никакие тесты для экономии энергии или потратить \(3^{a-1}\) энергии для подготовки \(a\) тестов для некоторого положительного целого \(a\).

У Фермера Джона есть \(D\) (\(1\le D\le 2\cdot 10^5\)) требований. Для \(i\)-го требования он говорит Беси, что в течение первых \(m_i\) минут она должна приготовить не менее чем \(b_i\) тестов (\(1\le m_i\le 10^6, 1 \leq b_i \leq 10^{12}\)).

Пусть \(e_i\) - минимальное количество энергии, которое необходимо Беси, чтобы удовлетворить первые \(i\) требований. Выведите \(e_1,\dots,e_D\) по модулю \(10^9+7\).

Deforestation

п»ї

Фермер Джон расширяет свою ферму! Он определил совершенное место - Красно-Чёрный Лес, который состоит из \(N\) деревьев (\(1 \le N \le 10^5\)) на числовой прямой, где \(i\)-ое дерево находится в позиции \(x_i\) (\(-10^9 \le x_i \le 10^9\)).

Закон по защите окружающей среды ограничивает, какие деревья может спилить ФД, освобождая место под свою ферму. Всего имеется \(K\) ограничений (\(1 \leq K \leq 10^5\)), указывающих, что должно быть как минимум \(t_i\) деревьев на отрезке \([l_i, r_i]\), включая конечные точки (\(-10^9 \le l_i, r_i \le 10^9\)). Гарантируется, что изначально Красно-Чёрный Лес удовлетворяет этим ограничениям.

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

ПР�МЕР ВВОДА:

3
7 1
8 4 10 1 2 6 7
2 9 3
7 2
8 4 10 1 2 6 7
2 9 3
1 10 1
7 2
8 4 10 1 2 6 7
2 9 3
1 10 4

ПР�МЕР ВЫВОДА:

4
4
3

Для первого подтеста, ФД может срезать первые 4 дерева, оставив деревья в точках \(x_i = 2, 6, 7\), чтобы удовлетворить ограничениям.

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

Для третьего подтеста, ФД может срезать не более \(3\) деревьев, потому что изначально \(7\) деревьев, однако второе ограничение требует чтобы он оставил как минимум \(4\) дерева не срезанными.

Авторы: Tina Wang, Jiahe Lu, Benjamin Qi

Job Completion

У Беси есть \(N\) (\(1\le N\le 2\cdot 10^5\)) работ для Вас. Если Вы выберете \(i\)-ую работу, её необходимо начать в момент времени \(s_i\) или до него и для её завершения требуется \(t_i\) единиц времени. (\(0\le s_i\le 10^{18}, 1\le t_i\le 10^{18}\)).

Какое максимальное количество работ Вы успеете выполнить? Время начинается с \(0\),и, если Вы начали работу, Вы сначала должны выполнить и только потом начинать другую работу.

Moo Route

В момент времени \(t=0\) Беси расположена в точке \(x=0\) на бесконечной числовой прямой. Она двигается влево или вправо каждую секунду. Однако после \(T\) секунд Беси возвращается в точку \(x=0\).

Фермер Нхой знает сколько раз Беси пересекала точки \(x=.5, 1.5, 2.5, \ldots, (N-1).5\), и это задаётся числами массива \(A_0,A_1,\dots,A_{N-1}\) (\(1\leq N \leq 10^5\), \(1 \leq A_i \leq 10^6\), \(\sum A_i\le 10^6\)). Беси никогда не попадает ни в \(x>N\) ни в \(x<0\).

В частности, маршрут Беси может быть представлен строкой символов \(T = \sum_{i=0}^{N-1} A_i\) \(L\) и \(R\), где \(i\)-ый символ представляет направление движения Беси во время \(i\)-ой секунды. Количество изменений направления движения определяется как количество \(LR\) плюс количество \(RL\).

Помогите ФН найти любой маршрут Беси, который соответствует массиву \(A\) и имеет минимальное количество изменений направления движения. Гарантируется существование как минимум одного такого маршрута.

Watching Mooloo

Беси любит смотреть шоу на сервисе Mooloo. Поскольку Беси очень занятая корова, она создаёт план на следующие \(N\) (\(1 \leq N \leq 10^5\)) дней в течение которых будет смотреть шоу. Mooloo - платный сервис и она хочет минимизировать оплату.

У Mooloo интересная система подписки: она стоит \(d + K\) денег (\(1\le K\le 10^9\)), чтобы подписаться на \(d\) последовательных дней. Вы можете начать подписку в любой день. И Вы можете начать новую подписку, если текущая подписка истекла. Определите минимальное количество денег, чтобы заплатить за просмотр шоу.

Train Scheduling

**Замечание: Ограничение по памяти для этой задачи 512MB, в два раза больше значения по умолчанию.**

Беси приняли на новую работу - диспетчером поездов. Имеется две железнодорожные станции \(A\) и \(B\). В связи с ограничением бюджета, эти станции соединены только одной дорогой. Если поезд отправляется от одной станции в момент времени \(t\), тогда он прибудет на другую станцию в момент времени \(t+T\) (\(1\le T\le 10^{12}\)).

Имеется \(N\) (\(1\le N\le 5000\)) поездов для которых нужно установить время отправки. \(i\)-ый поезд должен покинуть станцию \(s_i\) в момент времени $t_i или позже (\(s_i\in \{A, B\}, 0\le t_i\le 10^{12}\)). Запрещено иметь поезда, которые движутся в противоположных направлениях в один и тот же момент времени (поскольку они столкнутся). Однако разрешено иметь множество поездов, которые еду в одном направлении в одно и то же время (предполагаем, что поезда имеют пренебрежимо малые размеры)

Помогите Беси спланрировать времена отправления так, чтобы не было столкновений, а общая задержка была минимальной. Если поезд спланирован на убытие в момент времени \(a_i\ge t_i\), общая задержка определяется как \(\sum_{i=1}^N(a_i-t_i)\).

Cowntact Tracing 2

Фермер Джон выстроил в ряд свои \(N\) коров (\(1 \leq N \leq 3\cdot 10^5\)). К несчастью, стала распространяться болезнь.

Изначально некоторые коровы инфицированы. Каждую ночь инфицированная корова распространяет болезнь на коров соседних слева и справа, если они есть. Однажды инфицированная корова остаётся инфицированной.

После некоторого количества ночей ФД понял, что ситуация выходит из-под контроля поэтому он проверил своих коров, чтобы определить больных коров. Определите минимальное количество коров, которые могли быть больными в самом начале.

Apple Catching

Падают яблоки! В определённые моменты времени некоторое количество яблок падает в некоторые точки числовой прямой. В определённый момент времени некоторые коровы появляются на числовой прямой и НАЧИНАЮТ ловить яблоки.

Если яблоко падает на числовую прямую и корова его не поймала, оно исчезает бесследно. Если корова и яблоко прибыли в одно и то же время, корова ловит яблоко. Каждая корова может перемещаться на одну единицу за секунду. Если корова поймала яблоко, она покидает числовую прямую.

Сколько максимально яблок смогут поймать коровы, если будут действовать сообща оптимально?

Counting Liars

Корова Беси прячется где-то на числовой прямой. Каждая из \(N\) (\(1\le N\le 1000\)) других коров Фермера Джона имеет информацию, которой она делится с ФД: \(i\)-ая корова говорит, что Беси прячется в некоторой точке меньше либо равной to \(p_i\), или больше либо равной \(p_i\), (\(0\le p_i\le 10^9\)).

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

Sleeping in Class

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

ФД попросил Эльзу записывать количество раз, когда Беси засыпала на каждом занятии. Всего было \(N\) занятий (\(2\le N\le 10^5\)), и Эльза зафиксировала \(a_i\) (\(1\le a_i\le 10^{18}\)) засыпаний на \(i\)-ом занятии. Общее количество засыпаний на всех занятиях не превышает \(10^{18}\).

Эльза хочет представить дело так, что Беси засыпала одинаковое количество раз на каждом занятии.

Единственный способ Эльзы модифицировать свои записи - объединить два соседних занятия или разъединить одно занятие на два. Например, если \(a=[1,2,3,4,5],\) тогда если Эльза объединит второе и третье занятие, то лог станет \([1,5,4,5]\) Если Эльза выберет разделить третье занятие на два, то лог может стать одним из \([1,5,0,4,5]\), \([1,5,1,3,5]\), \([1,5,2,2,5]\), \([1,5,3,1,5]\), or \([1,5,4,0,5]\).

По заданным \(Q\) (\(1\le Q\le 10^5\)) кандидатам \(q_1,\ldots,q_Q\) для наименее любимых Беси чисел (\(1\le q_i\le 10^{18}\)), для каждого из них помогите Эльзе вычислить минимальное количество модификаций лога, чтобы все числа в нём стали одинаковыми.

Photoshoot 2

Фермер Джон выстроил в ряд своих \(N\) коров для фотографии.

Изначально коровы выстроились в порядке \(a_1,a_2,\ldots,a_N\) слева направо. Цель ФД выстроить их в порядке \(b_1,\ldots,b_N\) слева направо. Чтобы достичь своей цели, ФД может выполнить несколько модификаций порядка. Каждая модификация состоит в том, чтобы выбрать корову и переместить её влево на некоторое количество позиций.

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

Feeding the Cows

У Фермера Джона имеется \(N\) (\(1 \le {N} \le {10^5}\)) коров, каждая из которых имеет породу или Guernsey(G) или Holstein(H). Они выстроились в ряд заняв позиции \(1\dots N\).

Поскольку все коровы голодные, ФД решил выложить пакты с травой в некоторых позициях \(1\dots N\). Коровы разных пород едят разные типы травы. Каждый пакет травы должен содержать траву только одного типа (для G или для H). Он не может разместить пакеты с разной травой в одной и той же позиции. Каждый пакет травы может накормить неограниченное количество коров соответствующего типа.

Каждая корова готова пройти не более \(K\) (\(0 \le {K} \le N-1\)) позиций чтобы добраться до пакета с травой. Определите минимальное количество пакетов с травой, необходимое чтобы накормить всех коров. Любая конфигурация, удовлетворяющая указанным выше ограничениям, будет рассматриваться как корректная.

Closest Cow Wins

У Фермера Джона длинная ферма вдоль скоростной дороги, которую можно рассматривать как числовую прямую. Вдоль фермы имеется \(K\) травяных пастбищ \(1 \leq K \leq 2\cdot 10^5\)); \(i\)-ое пастбище расположено в позиции \(p_i\) и имеет величину вкусности \(t_i\) (\(0\le t_i\le 10^9\)). Фермер Нхой уже расположил свои \(M\) коров (\(1 \leq M \leq 2\cdot 10^5\)) в позициях \(f_1 \ldots f_M\). Все \(K+M\) этих чисел различны и находятся в интервале \([0,10^9]\).

ФД хочет выбрать \(N\) (\(1\le N\le 2\cdot 10^5\)) (не обязательно в целых числах) для размещения своих коров. Эти числа должны отличаться от позиций занимаемых коровами ФН, но они могут находится в позициях травяных пастбищ.

Корова какого фермера находится ближе к травяному пастбищу, тот и объявляется собственником этого пастбища. Если коровы обоих фремеров находятся на одинаковом расстоянии от пастбища, то оно объявляется принадлежащим ФН.

По заданным позициям коров ФН и вкусностям пастбищ определите максимальную вкусность суммарную, которой может добиться ФД оптимальным размещением своих коров.

Air Cownditioning

\(N\) коров очень чувствительны к температуре в амбаре. Некоторые любят температуру похолоднее, а другие - потеплее.

Амабар Фермера Джона содержит последовательность из \(N\) стойл, пронумерованных \(1 \ldots N\), каждое содержит ровно одну корову. \(i\)-ая корова предпочитает, чтобы температура в её стойле была \(p_i\), а прямо сейчас температура в её стойле \(t_i\). Для того чтобы угодить всем коровам, ФД установил новую систему кондиционирования, которая работает следующим образом. ФД посылает команды системе - увеличить или уменьшить температуру в некоторых подряд идущих стойлах на 1 (например, увеличить на 1 температуру в стойлах \(5 \ldots 8\)). Последовательность стойл может состоять из одного стойла.

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

Race

Беси участвует в гонке длиной \(K\) (\(1\le K\le 10^9\)) метров. Она начинает бежать со скоростью 0 метров в секунду. Каждую секунду она может увеличить свою скорость на 1 метр в секунду, оставить скорость неизменной или уменьшить скорость на 1 метр в секунду. Например, в первую секунду она может увеличить скорость на 1 метр в секунду и пробежать за эту секунду 1 метр, или оставить скорость - метров в секунду и пробежать 0 метров. Беси не может сделать свою скорость меньше нуля.

Беси всегда бежит к финишу и хочет финишировать после целого количества секунд. Кроме того, она не хочет прибежать слишком быстро, поэтому на финише её скорость не может превысить \(X\) (\(1 \leq X \leq 10^5\)) метров в секунду. Беси хочет узнать, как быстро она сможет закончить гонку для \(N\) (\(1 \leq N \leq 1000\)) различных величин \(X\).

Balancing Inversions

Беси и Эльза играют на битовом массиве \(A\) длиной \(2N\) (\(1 \leq N \leq 10^5\)). Счёт Беси - это количество инверсий в первой половине массива \(A\), а счёт Эльзы - количество инверсий во второй половине массива \(A\). Инверсия - это такая пара \(A[i]=1\) и \(A[j]=0\), что \(i<j\). Например, если массив состоит из блока 0, за которым следует блок 1, то инверсий нет. А массив в котором за блоком из \(X\) единиц следует блок из \(Y\) нулей, то имеется \(XY\) инверсий.

Фермер Джон остановился около игры и хочет узнать минимальное количество обменов между соседними элементами, которые нужно совершить, чтобы игра получила ничейный счёт. ФОРМАТ ВВОДА (файл balance.in): Первая строка ввода содержит \(N\), следующая строка содержит \(2N\) целых чисел каждое из которых равно 0 или 1. ФОРМАТ ВЫВОДА (файл balance.out): Выведите количество соседних обменов, которые нужно сделать, чтобы игра получила ничейный счёт.

Sleepy Cow Herding

\(N\) коров Фермера Джона бродят далеко от фермы. Ваша задача - собрать их в стадо.

Главное поле фермы представлено прямой, на которой каждая корова занимает некоторое положение в целочисленной координате. Изначально все \(N\) коров находятся в различных позициях. ФД хочет, чтобы они заняли соседние позиции (например 3,4,5,6,7,8).

В любой момент времени ФД может давать команду только одной из двух "крайних" коров (находящейся или в минимальной или в максимальной позиции среди всех коров). Когда ФД перемещает корову, он говорит ей перейти на любую незанятую позицию, так чтобы эта корова перестала быть крайней. Такие перемещения "сближают" коров вплоть до нужного результата.

Определите минимальное и максимальное количество таких перемещений, чтобы коровы заняли \(N\) последовательных позиций.

The Great Revegetation

Длительная засуха лишила травы \(N\) пастбищ Фермера Джона. Однако с приближением сезона дождей пришло время восстановить траву на пастбищах.

В сарае ФД есть четыре ведра, каждое хранит семена своего типа. ФД хочет посадить на каждом пастбище траву семенами одного из этих типов. ФД хочет каждой их своей коров различную диету. Каждая из его \(M\) коров имеет два любимых пастбища. И он хочет гарантировать, чтобы на каждой такой паре пастбищ была засеяна трава различных типов, и тогда каждая корова сможет выбирать из двух видов травы. ФД знает, что нет пастбища, которое нравится более чем трём коровам.

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

Lemonade Line

Сегодня на ферме жаркий летний день и Фермер Джон развозит лимонад своим \(N\) коровам. Все \(N\) коров (последовательно пронумерованных \(1 \dots N\)) любят лимонад, но некоторые из них любят больше чем другие. В частности, корова \(i\) готова подождать не более \(w_i\) коров прежде чем получит свой лимонад. Прямо сейчас все \(N\) коров на полях, но вскоре ФД позвонит в колокол и коровы побегут к нему. Все прибудут до того, как он начнёт раздавать лимонад, но никакие две коровы не прибудут в одно и то же время. Более того, когда корова \(i\) прибывает, она становится в очередь если и только если в очереди находится не более \(w_i\) коров.

ФД хочет подготовить заранее некоторое количество лимонада, но он не хочет быть нерасчётливым. Количество коров, которые станут в очередь зависит от порядка, в котором они прибывают. Помогите ему определить минимальное количество коров, которые станут в очередь.

Lifeguards

Фермер Джон открыл бассейн для своих коров, чтобы они там отдыхали и потом давали больше молока.

Чтобы обеспечить безопасность, он нанял \(N\) коров спасателями, каждый из которых работает в течение некоторого интервала времени в течение дня. Для простоты, бассейн открыт с момента времени \(t=0\) до момента времени \(10^9\) каждый день. Поэтому каждый интервал может быть описан двумя целыми числами - временем начала и конца работы спасателя. Например, спасатель, начинающий в момент времени \(t = 4\) и завершающий в момент времени \(t = 7\), покрывает интервал в три единицы времени.

К несчастью, ФД нанял на \(K\) спасателей больше чем может платить зарплату. При условии, что он должен уволить ровно \(K\) спасателей, какой максимальный интервал времени, будет покрыт оставшимися спасателями? Интервал времени покрыт, если присутствует хоть один спасатель в это время.

Snow Boots

На ферме зима и значит много снега! Имеется \(N\) фрагментов на дорожке от фермы к амбару, последовательно пронумерованных \(1 \dots N\), и фрагмент \(i\) покрыт \(f_i\) футами снега.

Фермер Джон начинает с фрагмента \(1\) и должен достичь фрагмента \(N\), чтобы разбудить своих коров. Фрагмент \(1\) защищён крышей фермы, а фрагмент \(N\) - крышей амбара, поэтому на них нет снега. Но чтобы ходить по другим фрагментам ФД должен носить ботинки.

У ФД есть \(B\) пар ботинок, пронумерованных \(1 \dots B\). Некоторые из них тяжёлые, а некоторые полегче. В частности, пара \(i\) позволяет ФД ходить по снегу не более \(s_i\) футов глубины и позволяет ФД продвигаться на расстояние \(d_i\) вперёд на каждом шагу.

К несчастью, ботинки упакованы таким образом, что ФД может взять только самую верхнюю пару в любой момент времени. Поэтому в любой момент времени ФД может или положить наверх пару ботов (отказываясь от старых ботов) или снять верхнюю пару ботов, делая новую пару доступной).

ФД может менять ботинки только когда стоит на фрагменте. Если он стоит на фрагменте, то и те ботинки, которые он снимает, и те ботинки, которые он надевает, должны быть выше снега, как минимум на \(f\) футов. Промежуточные пары ботинок, которые он снимает из стопки ботинок не одевая, могут не удовлетворять этому ограничению.

Помогите ФД минимизировать отбросы, определив минимальное количество пар ботов, которые он должен снять из стопки не одевая, чтобы достичь амбара. Вы можете считать, что изначально на ФД нет никаких ботинок.

Taming the Herd

Однажды утром Фермер Джон проснулся от звуков дробления древесины. Это коровы ломали амбар.

ФД рассердился. Он приделал к стене счётчик дней с последнего слома. Если слом случился утром, счётчик покажет 0. Если последний слом случился 3 дня назад, счётчик показывает 3. ФД тщательно записывал значение счётчика каждый день.

В конце года ФД решил действовать. Однако с логом некоторые проблемы.

ФД хочет определить, сколько слово зафиксировано. Однако он подозревает, что коровы подделали его лог и всё в чём он уверен, что он начало лог в день слома. Помогите ему определить, для каждого количества сломов какое минимальное количество записей должно быть подделано.

Sort It Out

\(N\) (\(1 \leq N \leq 10^5\)) Є®а®ў ”Ґа¬Ґа  „¦®­  (а §«Ёз­® Ё¤Ґ­вЁдЁжЁа®ў ­­ле \(1 \ldots N\)), ўлбв஥­л ў ап¤. ”„ «оЎЁв, Є®Ј¤  ҐЈ® Є®а®ўл ўлбв஥­л Ї® ў®§а бв ­Ёо, ­® ᥩз б нв® ­Ґ в Є. ”„ ўл§лў Ґв Є®а®ўл Ї® ®¤­®©. Љ®Ј¤  Є®а®ў  ўл§ў ­ , ®­  Їа®ўҐапҐв, Ґб«Ё Є®а®ў  ­ҐЇ®б।б⢥­­® бЇа ў  ®в ­Ґс Ё¬ҐҐв ¬Ґ­миЁ© ID, в®Ј¤  ®­Ё ¬Ґ­повбп ¬Ґбв ¬Ё. ‡ вҐ¬, Ґб«Ё Є®а®ў  ­ҐЇ®б।б⢥­­® б«Ґў  ®в ­Ґс Ё¬ҐҐв Ў®«миЁ© ID, ®­Ё ¬Ґ­повбп ¬Ґбв ¬Ё. Љ®а®ў  ®бв ­ ў«Ёў Ґвбп ў в®зЄҐ, Є®Ј¤  Є®а®ў  б«Ґў  ®в ­Ґс Ё¬ҐҐв ¬Ґ­миЁ© ­®¬Ґа,   Є®а®ў  бЇа ў  ®в ­Ґс Ё¬ҐҐв Ў®«миЁ© ­®¬Ґа.

”„ е®зҐв ўлЎа вм Ї®¤¬­®¦Ґбвў® Є®а®ў, Ё § вҐ¬ Їа®ЁвҐаЁа®ў вмбп Ї® н⮬㠯®¤¬­®¦Ґбвўг, ўл§лў п Є ¦¤го Ё§ нвЁе Є®а®ў Ї® ®зҐаҐ¤Ё (ў Ї®ап¤ЄҐ ў®§а бв ­Ёп Ёе ID), ®Їпвм Ё ®Їпвм ¤® вҐе Ї®а, Ї®Є  ўбҐ Є®а®ўл ­Ґ бв ­гв ®вб®авЁа®ў ­л. Ќ ЇаЁ¬Ґа, Ґб«Ё ®­ ўлЎҐаҐв Ї®¤¬­®¦Ґбвў® Є®а®ў б ID \(\{2, 4, 5\}\), в® ®­ б­ з «  ўл§®ўҐв Є®а®ўг \(2\), § вҐ¬ Є®а®ўг \(4\), § вҐ¬ Є®а®ўг \(5\). …б«Ё ўбҐ \(N\) Є®а®ў Ґйс ­Ґ ®вб®авЁа®ў ­л, ®­ Ўг¤Ґв ўл§лў вм нвЁе Є®а®ў ®Їпвм Ё ®Їпвм, бЄ®«мЄ® ­г¦­® а §.

”„ е®зҐв ¬Ё­Ё¬Ё§Ёа®ў вм а §¬Ґа нв®Ј® ¬­®¦Ґбвў . Ѓ®«ҐҐ в®Ј®, Ї®бЄ®«мЄг ®­ бзЁв Ґв зЁб«® \(K\) бз бв«Ёўл¬, Ї®¬®ЈЁвҐ Ґ¬г ®ЇаҐ¤Ґ«Ёвм \(K\)-®Ґ «ҐЄбЁЄ®Ја дЁзҐбЄЁ ¬Ё­Ё¬ «м­®Ґ Ї®¤¬­®¦Ґбвў® ¬Ё­Ё¬ «м­®Ј® а §¬Ґа  в Є®Ґ, зв® ўл§лў п Ї®б«Ґ¤®ў вҐ«м­® Є®а®ў нв®Ј® Ї®¤¬­®¦Ґбвў  ­г¦­®Ґ Є®«ЁзҐбвў® а § ¬®¦­® ®вб®авЁа®ў вм ўбҐе Є®а®ў.

Џ®¤¬­®¦Ґбвў® \(S\) Ё§ \(\{1,\dots,N\}\) ­ §лў Ґвбп «ҐЄбЁЄ®Ја дЁзҐбЄЁ ¬Ґ­миҐ, 祬 Ї®¤¬­®¦Ґбвў® \(T\) Ґб«Ё бЇЁб®Є н«Ґ¬Ґ­в®ў ў \(S\) (ў Ї®ап¤ЄҐ ў®§а бв ­Ёп) «ҐЄбЁЄ®Ја дЁзҐбЄЁ ¬Ґ­миҐ, зҐ бЇЁб®Є н«Ґ¬Ґ­в®ў Ё§ \(T\) (ў Ї®ап¤ЄҐ ў®§а бв ­Ёп). Ќ ЇаЁ¬Ґа, \(\{1, 3, 6\}\) «ҐЄбЁЄ®Ја дЁзҐбЄЁ ¬Ґ­миҐ, 祬 \(\{1, 4, 5\}\).

ЋжҐ­Ёў ­ЁҐ: ‚ вҐбв е ­  \(3/16\) Ў ««®ў \(N \leq 6\) and \(K = 1\). ‚ ¤®Ї®«­ЁвҐ«м­ле вҐбв е ­  \(5/16\) Ў ««®ў, \(K = 1\). ‚ ¤®Ї®«­ЁвҐ«м­ле вҐбв е ­  \(8/16\) Ў ««®ў, ­Ґв ¤агЈЁе ®Ја ­ЁзҐ­Ё©.

Џђ€Њ…ђ ‚‚Ћ„Ђ:

4 1
4 2 1 3

Џђ€Њ…ђ ‚›‚Ћ„Ђ:

2
1
4

Њл ­ зЁ­ Ґ¬ б ¬ ббЁў  \(\mathtt{\:4\:\; 2\:\; 1\:\; 3\:}\). Џ®в®¬ ”„ ўл§лў Ґв Є®а®ўг б ID 1Ў Ї®«гзЁвбп ¬ ббЁў \(\mathtt{\:1\:\; 4\:\; 2\:\; 3\:}\). Џ®в®¬ ”„ ўл§лў Ґв Є®а®ўг б ID 4 Ї®«гзЁвбп ¬ ббЁў \(\mathtt{\:1\:\; 2\:\; 3\:\; 4\:}\). ‚ нв®© в®зЄҐ ¬ ббЁў ®вб®авЁа®ў ­.

Problem credits: Spencer Compton

Haybale Feast

Фермер Джон готовит деликатесную еду для своих коров. В его амбаре имеется \(N\) стогов сена (\(1 \le N \le 100,000\)). \(i\)-ый стог имеет опредённый вкус \(F_i\) (\(1 \le F_i \le 10^9\)) и определённую пряность \(S_i\) (\(1 \le S_i \le 10^9\)).

Еда будет представлять собой непрерывный интервал, содержащий один или более последовательных стогов сена (нельзя менять их порядок). Общий вкус еды равен сумме вкусов на интервале. Общая пряность еды - максимум из пряностей на интервале.

ФД хочет определить минимальную пряность, кторую можно достичь, чтобы вкус был не менее \(M\) (\(1 \le M \le 10^{18}\)).