Бинарный поиск

47 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Медиана объединений#56019
Дано N упорядоченных по неубыванию последовательностей целых чисел (т.е. каждый следующий элемент больше либо равен предыдущему), в каждой из последовательностей ровно L элементов. Для каждых двух последовательностей выполняют следующую операцию: объединяют их элементы (в объединенной последовательности каждое число будет идти столько раз, сколько раз оно встречалось суммарно в объединяемых последовательностях), упорядочивают их по неубыванию и смотрят, какой элемент в этой последовательности из 2L элементов окажется на месте номер L (этот элемент называют левой медианой).

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

Входные данные
Сначала вводятся числа N и L (2≤N≤100, 1≤L≤300). В следующих N строках задаются параметры, определяющие последовательности.

Каждая последовательность определяется пятью целочисленными параметрами: x1, d1, a, c, m. Элементы последовательности вычисляются по следующим формулам: x1 нам задано, а для всех i от 2 до L: x1 = x1–1+di-1. Последовательность di определяется следующим образом: d1 нам задано, а для i≥2 di=((a*di-1+c) mod m), где mod – операция получения остатка от деления (a*di-1+c) на m.

Для всех последовательностей выполнены следующие ограничения: 1≤m≤40000, 0≤a<m, 0≤c<m, 0≤d1<m. Гарантируется, что все члены всех последовательностей по модулю не превышают 109.

Выходные данные
В первой строке выведите медиану объединения 1-й и 2-й последовательностей, во второй строке — объединения 1-й и 3-й, и так далее, в (N-1)-ой строке — объединения 1-й и N-ой последовательностей, далее медиану объединения 2-й и 3-й, 2-й и 4-й, и т.д. до 2-й и N-ой, затем 3-й и 4-й и так далее. В последней строке должна быть выведена медиана объединения (N–1)-й и N-ой последовательностей.
Бинарный поиск в массивеБинарный поиск по ответу
✓ 1✗ 0—Войти и решать
Медиана объединений#55404
Дано N упорядоченных по неубыванию последовательностей целых чисел (т.е. каждый следующий элемент больше либо равен предыдущему), в каждой из последовательностей ровно L элементов. Для каждых двух последовательностей выполняют следующую операцию: объединяют их элементы (в объединенной последовательности каждое число будет идти столько раз, сколько раз оно встречалось суммарно в объединяемых последовательностях), упорядочивают их по неубыванию и смотрят, какой элемент в этой последовательности из 2L элементов окажется на месте номер L (этот элемент называют левой медианой).

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

Входные данные
Сначала вводятся числа N и L (2≤N≤200, 1≤L≤50000). В следующих N строках задаются параметры, определяющие последовательности.

Каждая последовательность определяется пятью целочисленными параметрами: x1, d1, a, c, m. Элементы последовательности вычисляются по следующим формулам: x1 нам задано, а для всех i от 2 до L: x1 = x1–1+di-1. Последовательность di определяется следующим образом: d1 нам задано, а для i≥2 di=((a*di-1+c) mod m), где mod – операция получения остатка от деления (a*di-1+c) на m.

Для всех последовательностей выполнены следующие ограничения: 1≤m≤40000, 0≤a<m, 0≤c<m, 0≤d1<m. Гарантируется, что все члены всех последовательностей по модулю не превышают 109.

Выходные данные
В первой строке выведите медиану объединения 1-й и 2-й последовательностей, во второй строке — объединения 1-й и 3-й, и так далее, в (N-1)-ой строке — объединения 1-й и N-ой последовательностей, далее медиану объединения 2-й и 3-й, 2-й и 4-й, и т.д. до 2-й и N-ой, затем 3-й и 4-й и так далее. В последней строке должна быть выведена медиана объединения (N–1)-й и N-ой последовательностей.
Бинарный поиск в массивеБинарный поиск по ответу
✓ 1✗ 4—Войти и решать
Выборы#53910

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

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

Чтобы повлиять на исход выборов, бизнесмен собирается выделить деньги на агитационную работу среди жителей страны. Исследование рынка показало, что для того чтобы один житель сменил свои политические воззрения, требуется потратить одну условную единицу. Кроме того, чтобы \(i\)-я партия в случае победы сформировала правительство, которое будет действовать в интересах бизнесмена, необходимо дать лидеру этой партии взятку в размере \(p_i\) условных единиц. При этом некоторые партии оказались идеологически устойчивыми и не согласны на сотрудничество с бизнесменом ни за какие деньги.

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

Формат входных данных
Первая строка содержит целое число \(n\) — количество партий (\(1 \le n \le 10^5\)). Следующие \(n\) строк описывают партии. Каждая из этих строк содержит по два целых числа: \(v_i\) — количество жителей, которые собираются проголосовать за эту партию перед началом агитационной компании, и \(p_i\) — взятка, которую необходимо дать лидеру партии для того, чтобы сформированное ей в случае победы правительство действовало в интересах бизнесмена (\(1 \le v_i \le 10^6\), \(1 \le p_i \le 10^6\) или \(p_i = -1\)). Если партия является идеологически устойчивой, то \(p_i\) равно \(-1\). Гарантируется, что хотя бы одно \(p_i\) не равно \(-1\).

Формат выходных данных
На первой строке выведите минимальную сумму, которую придется потратить бизнесмену. На второй строке выведите номер партии, лидеру которой следует дать взятку. На третьей строке выведите \(n\) целых чисел — количество голосов, которые будут отданы за каждую из партий после осуществления операции. Если оптимальных решений несколько, выведите любое.

 
Бинарный поискБинарный поиск по ответуБыстрая сортировка
✓ 2✗ 18—Войти и решать
3.5. Алекс и настройка радиосвязи#100096

Алекс настраивает связь между исследовательскими станциями. Есть n станций и m возможных двусторонних каналов. Канал между станциями u и v начинает работать, если общая настройка мощности P не меньше указанного для него порога w.

Сообщение нужно передать со станции s на станцию t, использовав не более k каналов подряд. Использование одного канала считается одним переходом. Промежуточные станции могут пересылать сообщение.

Найдите минимальную целую мощность P ≥ 0, при которой это возможно. Если подходящего маршрута нет даже при работающих всех каналах, сообщите об этом.

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

Первая строка содержит пять целых чисел n, m, k, s, t (2 ≤ n ≤ 50 000, 0 ≤ m ≤ 100 000, 1 ≤ k ≤ n − 1, 1 ≤ s, t ≤ n, s ≠ t).

Следующие m строк содержат u, v, w (1 ≤ u, v ≤ n, u ≠ v, 0 ≤ w ≤ 109). Между одной парой станций не более одного канала.

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

Выведите минимальную мощность либо −1, если передать сообщение за допустимое число переходов невозможно.

Пояснения к примерам

Пример 1. При мощности 7 подходит маршрут 1 → 3 → 5. При мощности 6 доступен маршрут 1 → 3 → 4 → 5, но он слишком длинный.

Пример 2. Связь существует, но сообщение должно пройти два канала, а разрешён только один.

АлгоритмыБинарный поиск по ответуОбход в ширину
—Войти и решать
3.2. Алекс и датчики на тропе#100093

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

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

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

Первая строка содержит целые числа n и k (2 ≤ k ≤ n ≤ 200 000). Вторая строка содержит n различных целых координат xᵢ (0 ≤ xᵢ ≤ 109) в произвольном порядке.

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

Выведите максимальное минимальное расстояние.

Пояснения к примерам

Пример 1. Можно поставить датчики в точках 1, 4 и 8. Минимальное расстояние равно 3.

Пример 2. Нужно занять оба места.

АлгоритмыБинарный поиск по ответуЖадный алгоритмИспользование сортировки
—Войти и решать
2.4. Алекс и сеансы в лабораториях#100090

На научной смене Алекс может посетить n лабораторных сеансов. Сеанс i начинается в момент sᵢ, заканчивается в момент fᵢ и приносит vᵢ исследовательских баллов. Баллы начисляются только за полностью посещённый сеанс.

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

Алекс может выбирать любые сеансы и пропускать остальные. Найдите максимальную сумму баллов.

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

Первая строка содержит целое число n (1 ≤ n ≤ 200 000). Следующие n строк содержат по три целых числа sᵢ, fᵢ, vᵢ (0 ≤ sᵢ < fᵢ ≤ 109, 1 ≤ vᵢ ≤ 109). Сеансы перечислены в произвольном порядке; совпадения времён допускаются.

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

Выведите максимальное количество баллов, которое сможет набрать Алекс.

Пояснения к примерам

Пример 1. Подходят сеансы 1, 3 и 5: 7 + 9 + 10 = 26 баллов.

Пример 2. Окончание первого совпадает с началом второго; можно посетить оба.

АлгоритмыБинарный поиск в массивеДинамическое программирование: один параметрТеория расписаний
—Войти и решать
2.1. Алекс и мастерская значков#100087

К фестивалю Алекс готовит k значков. В мастерской работают n независимых станков. В момент 0 Алекс включает их все.

Станок i сначала прогревается sᵢ секунд, затем изготавливает один значок за pᵢ секунд. Его первый значок готов в момент sᵢ + pᵢ, второй — в момент sᵢ + 2pᵢ и так далее. Между значками станок не останавливается. Материалов достаточно.

Найдите самый ранний целый момент времени, когда суммарно будет готово не менее k значков. Значок, завершённый ровно в этот момент, уже считается готовым.

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

Первая строка содержит целые числа n и k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 109).

Следующие n строк содержат по два целых числа sᵢ и pᵢ (0 ≤ sᵢ ≤ 109, 1 ≤ pᵢ ≤ 109).

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

Выведите одно целое число — искомый момент времени в секундах.

Пояснения к примерам

Пример 1. К моменту 8 готовы 2 + 2 = 4 значка, а к моменту 9 — 3 + 2 = 5.

Пример 2. Значки единственного станка готовы в моменты 9, 13 и 17.

АлгоритмыБинарный поиск по ответу
—Войти и решать
1.5. Алекс и ограниченный абонемент#100086

Алекс выбирает мастер-классы научного фестиваля. Мастер-класс i идёт с момента sᵢ до момента fᵢ и приносит vᵢ баллов опыта. Чтобы получить баллы, его нужно посетить целиком.

Абонемент Алекса позволяет посетить не более K мастер-классов. Одновременно находиться на двух нельзя. Если один закончился ровно в момент начала другого, можно посетить оба. Переходы между аудиториями мгновенны.

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

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

Первая строка содержит целые числа n и K (1 ≤ n ≤ 50 000, 1 ≤ K ≤ min(30, n)). Следующие n строк содержат целые числа sᵢ, fᵢ, vᵢ (0 ≤ sᵢ < fᵢ ≤ 109, 1 ≤ vᵢ ≤ 109). Порядок произвольный; совпадения времён допустимы.

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

Выведите максимальную сумму баллов.

Пояснения к примерам

Пример 1. Лучше посетить только шестой мастер-класс. Цепочка 1, 3, 5 дала бы 26 баллов, но требует трёх посещений.

Пример 2. Из трёх совместимых мастер-классов нужно выбрать два: второй и третий.

АлгоритмыБинарный поиск в массивеДинамическое программирование: два параметраТеория расписаний
—Войти и решать
1.3. Алекс и доставка экспонатов#100084

Алекс должен перевезти n ящиков с экспонатами. На складе ящики стоят в очереди, массы ящиков равны a₁, …, aₙ.

За один рейс Алекс забирает несколько первых оставшихся ящиков. Менять порядок и пропускать ящики нельзя. Каждый ящик перевозится целиком, ровно один раз. Масса груза в одном рейсе не должна превышать грузоподъёмность машины C.

Алекс может сделать не более k рейсов. Найдите минимальную целую грузоподъёмность C, которой хватит, чтобы перевезти все ящики.

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

Первая строка содержит целые числа n и k (1 ≤ k ≤ n ≤ 200 000). Вторая строка содержит n целых чисел aᵢ (1 ≤ aᵢ ≤ 109).

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

Выведите минимальную грузоподъёмность.

Пояснения к примерам

Пример 1. Подходят рейсы [4, 2], [7], [3, 5]. При грузоподъёмности 7 понадобятся четыре рейса.

Пример 2. Единственный рейс должен вместить все ящики.

АлгоритмыБинарный поиск по ответуЖадный алгоритм
—Войти и решать
Cow Dance Show#90399
После нескольких месяцев репетиций, коровы готовы дать ежегодное танцевальное представление - балет "Cowpelia".

Остался непрояснённым только размер сцены. Сцена размера \(K\) может выдержать \(K\) коров, танцующих одновременно. \(N\) коров в стаде (\(1 \leq N \leq 10,000\)) пронумерованы последовательно \(1 \ldots N\) в порядке, в котором они должны появиться на сцене во время танца. Каждая корова \(i\) планирует танцевать определённое время \(d(i)\). Изначально коровы \(1 \ldots K\) появляются на сцене и начинают танцевать. Когда первая из этих коров завершит свой танец, она покидает сцену и корова \(K+1\) немедленно начинает танцевать и т.д. Поэтому всегда \(K\) коров танцуют, за исключением последнего отрезка шоу, когда коровы уходят, но не добавляются. Шоу завершается, когда последняя корова завершит свой танец в момент времени \(T\).

Понятно, что чем больше значение \(K\), тем меньше время \(T\). Поскольку шоу не может длится очень долго, вам на вводе даётся верхняя граница \(T_{max}\), указывающая максимально возможное значение величины \(T\). Ваша задача - определить минимально возможное подходящее значение \(K\).

ФОРМАТ ВВОДА (файл cowdance.in):

Первая строка ввода содержит \(N\) и \(T_{max}\), где \(T_{max}\) - целое число, не более 1 000 000.

Следующие \(N\) строк задают длительности танцев \(d(1) \ldots d(N)\) для коров \(1 \ldots N\). Каждое из \(d(i)\) - целое число в интервале \(1 \ldots 100,000\).

Гарантируется, что если \(K=N\), шоу закончится вовремя.

ФОРМАТ ВЫВОДА (файл cowdance.out):

Выведите наименьшее возможное значение \(K\) такое, что танцевальное шоу закончится не более чем через \(T_{max}\) единиц времени.

Бинарный поиск по ответуЖадный алгоритмОчередь
—Войти и решать
Building a Tall Barn#90396
Фермер Джон строит новый \(N\)-этажный амбар с помощью своих \(K\) коров (\(1 \leq N \leq K \leq 10^{12}\) и \(N \leq 10^5\)). Чтобы сделать работу быстрее ему нужно оптимально распределить работу между коровами.

Каждая корова должна быть назначена на работу ровно на один этаж. И на каждый этаж должна быть назначена хотя бы одна корова. \(i\)-ый этаж требует выполнения \(a_i\) единиц работы , каждая корова завершает одну единицу работы ровно за час. Поэтому если \(c\) коров работают на этаже \(i\), то они выполнят всю работу ровно за \(a_i / c\) единиц времени. Из соображений безопасности, этаж \(i\) должен быть завершён прежде чем начнётся работа на этаже \(i+1\).

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

ФОРМАТ ВВОДА (файл tallbarn.in):

Первая строка ввода содержит \(N\) и \(K\).

Следующие \(N\) строк содержат \(a_1 \ldots a_N\), каждое - положительное целое не более чем \(10^{12}\).

ФОРМАТ ВЫВОДА (файл tallbarn.out):

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

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

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

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

ФОРМАТ ВВОДА (файл angry.in):

Первая строка ввода содержит \(N\) (\(1 \leq N \leq 50,000\)) и \(K\) (\(1 \leq K \leq 10\)). Каждая из оставшихся \(N\) строк содержит целые числа \(x_1 \ldots x_N\) (каждое в интервале \(0 \ldots 1,000,000,000\)).

ФОРМАТ ВЫВОДА (файл angry.out):

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

Бинарный поиск по ответуЖадный алгоритмЗадачи на моделирование
—Войти и решать
Angry Cows#90381
Беси придумала игру. Игрок бросает корову на одномерную сцену, состоящую из множества стогов сена, расположенных в различных точках числовой прямой. После приземления коровы может возникнуть цепная реакция взрывов. Цель - используя одну корову, начать цепную реакцию так, чтобы взорвать все стоги сена.

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

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

ФОРМАТ ВВОДА (файл angry.in):

Первая строка ввода содержит \(N\) (\(2 \leq N \leq 50,000\)). Оставшиеся \(N\) строк содержат целые числа \(x_1 \ldots x_N\) (каждое в диапазоне \(0 \ldots 1,000,000,000\)).

ФОРМАТ ВЫВОДА (файл angry.out):

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

Бинарный поиск по ответу
—Войти и решать
Counting Haybales#90366
Фермер Джон разместил свои \(N\) (\(1 \leq N \leq 100,000\)) стогов сена в различных точках одномерной дороги вдоль его фермы. Вам требуется ответить на \(Q\) (\(1 \leq Q \leq 100,000\)) запросов, о том сколько стогов сена находится внутри указанного участка дороги.

ФОРМАТ ВВОДА (файл haybales.in):

Первая строка содержит \(N\) и \(Q\).

Следующая строка содержит \(N\) различных целых чисел, каждое в интервале \(0 \ldots 1,000,000,000\), указывающих местоположения стогов сена.

Каждая из последующих \(Q\) строк содержит два целых числа \(A\) и \(B\) (\(0 \leq A \leq B \leq 1,000,000,000\)) задающих запрос на количество стогов сена между \(A\) и \(B\), включительно.

ФОРМАТ ВЫВОДА (файл haybales.out):

Вы должны вывести \(Q\) строк. Для каждого запроса выведите количество стогов сена в соответствующем интервале.

Бинарный поиск в массивеИспользование сортировки
—Войти и решать
Moocast#90361
\(N\) (\(1 \leq N \leq 1000\)) коров Фермера Джона хотят организовать безопасную систему для передачи важных сообщений.

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

Коровам нужно решить сколько денег необходимо потратить на "воки-токи". Если они потратят \$X, они получат "воки-токи", способно передавать на расстояние до \(\sqrt{X}\). То есть, квадрат расстояния между коровами стоит не более \(X\) чтобы обеспечить их коммуникацией.

Помогите коровам определить минимальное целое \(X\) такое, что сообщение от любой коровы сможет достичь любой другой коровы.

ФОРМАТ ВВОДА (файл moocast.in):

Первая строка ввода содержит \(N\).

Каждая из \(N\) последующих строк содержит \(x\) и \(y\) координаты одной коровы. И то и другое - целое в интервале \(0 \ldots 25,000\).

ФОРМАТ ВЫВОДА (файл moocast.out):

Напишите в одну строку целое \(X\) - минимальное количество денег, которое коровы должны потратить на "воки-токи"

Бинарный поиск по ответуграфыПоиск компонент связности
—Войти и решать
Wormhole Sort#90113
Коровы Фермера Джона устали от ежедневных сортировок перед выходом из амбара. Они получили Ph.D по квантовой физике и готовы ускорить этот процесс.

Этим утром, как обычно \(N\) коров (\(1 \leq N \leq 10^5\)), последовательно пронумерованных \(1 \dots N\), находятся в амбаре на различных позициях, также пронумерованных \(1 \dots N\), так что корова \(i\) находится в позиции \(p_i\). Однако этим утром имеется \(M\) туннелей (\(1 \leq M \leq 10^5\)), которые пронумерованы \(1 \dots M\), при этом туннель \(i\) двунаправленно связывает позиции \(a_i\) и \(b_i\) и имеет ширину \(w_i\) ( \(1\le a_i,b_i\le N, a_i\neq bi, 1\le w_i\le 10^9\) ).

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

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

 

ОЦЕНИВАНИЕ:

 

  • Тесты 3-5 удовлетворяют ограничениям \(N,M\le 1000.\)
  • Тесты 6-10 не имеют дополнительных ограничений.

 

 

ФОРМАТ ВВОДА:

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

Вторая строка содержит \(N\) целых чисел \(p_1, p_2, \dots, p_N\). Гарантируется, что \(p\) есть перестановка чисел \(1\ldots N.\)

Для каждого \(i\) между \(1\) и \(M\), строка \(i+2\) содержит целые числа \(a_i\), \(b_i\), и \(w_i\).

 

ФОРМАТ ВЫВОДА:

Одно целое число: наибольшая минимальная ширина туннеля, в которую поместится коров во время процесса сортировки. Если коровы не используют туннели во время сортировки выведите \(-1\).

 

Бинарный поиск по ответуПоиск компонент связности
✓ 1✗ 0—Войти и решать
Loan Repayment#90112
Фермер Джон должен Беси \(N\) галлонов молока (\(1\le N\le 10^{12}\)). Он должен вернуть ей молоко в течение \(K\) дней. Однако он не хочет отдавать молоко слишком быстро. С другой стороны, он должен показывать прогресс в возвращении долга. Поэтому он должен возвращать Беси не менее \(M\) галлонов молока (\(1\le M\le 10^{12}\)) каждый день.

ФД собирается делать так. Он выбирает положительное целое число \(X\). А затем повторяет следующую процедуру каждый день:

  1. Предположим, что ФД уже отдал Беси \(G\) галлонов молока, он вычисляет \(\frac{N-G}{X}\) с округлением вверх. Назовём это число \(Y\).
  2. Если \(Y\) меньше чем \(M\), то устанавливает \(Y\) равным \(M\).
  3. Даёт Беси \(Y\) галлонов молока.

Определите максимальное \(X\) такое, что если ФД будет следовать этой процедуре, то ФД отдаст Беси не менее \(N\) галлонов молока после \(K\) дней (\(1\le K\le 10^{12}\)).

ОЦЕНИВАНИЕ:

  • Тесты 2-4 удовлетворяют ограничению \(K\le 10^5.\)
  • Тесты 5-11 не имеют дополнительных ограничений.

ФОРМАТ ВВОДА (файл loan.in):

Единственная строка ввода содержит три разделённых пробелом целых положительных числа \(N\), \(K\), \(M\) удовлетворяющих \(K\cdot M<N\).

ФОРМАТ ВЫВОДА (файл loan.out):

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

Бинарный поиск по ответуЗадачи на моделирование
—Войти и решать
Milking Order#90027
\(N\) коров (\(1 \leq N \leq 10^5\)), фермера Джона, пронумерованных \(1 \ldots N\), разработали социальную иерархию, в соответствии с которой ФД доит их каждое утро.

ФД сделал \(M\) наблюдений об этой структуре (\(1 \leq M \leq 50,000\)). Каждое наблюдение - упорядоченный список некоторых из его коров, указывающий что их нужно доить именно в таком порядке. Например список 2 5 1 означает, он должен подоить корову 2, некоторое время спустя - корову 5 и некоторое время после - корову 1.

Наблюдения ФД приоритезированы, поэтому его цель - максимизировать значение \(X\) так, чтобы выполнились условия первых \(X\) наблюдений. Если несколько порядков дойки могут удовлетворять \(X\) наблюдениям, он выбирает тот, в котором корова с меньшим номером доится раньше. Иными словами, если несколько порядков дойки удовлетворяют этим условиям, ФД выбирает лексикографически наименьший. Порядок \(x\) является лексикографически меньшим, чем порядок \(y\), если для некоторого \(j\), , \(x_i = y_i\) для всех \(i < j\) и \(x_j < y_j\) (другими словами два порядка идентичны до некоторой точки, в которой \(x\) меньше чем \(y\)).

Помогите ФД определить наилучший порядок дойки его коров.

ФОРМАТ ВВОДА (файл milkorder.in):

Первая строка содержит числа \(N\) и \(M\). Каждая из следующих \(M\) строк описывает одно наблюдение. Строка \(i+1\) описывает наблюдение \(i\) и начинается с количества коров \(m_i\) в этом наблюдении, за которым следует список из \(m_i\) целых чисел, определяющих порядок коров в этом наблюдении. Сумма \(m_i\) не превышает \(200,000\).

ФОРМАТ ВЫВОДА (файл milkorder.out):

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

Бинарный поиск по ответуграфыТопологическая сортировка
—Войти и решать
Convention#89997
На ферме Джона состоится съезд по поеданию травы.

Коровы со всего мира прибывают в местный аэропорт, чтобы посетить съезд и поесть траву. А именно \(N\) (\(1 \leq N \leq 10^5\)) коров прибывают в аэропорт, и корова \(i\) прибывает в момент времени \(t_i\) (\(0 \leq t_i \leq 10^9\)). ФД организовал \(M\) (\(1 \leq M \leq 10^5\)) автобусов для транспортировки коров из аэропорта. Каждый автобус может вместить до \(C\) (\(1 \leq C \leq N\)) коров. ФД ждёт вместе с автобусами в аэропорту и собирается распределить прибывающих коров по автобусам. Автобус убывает из аэропорта в момент, когда прибывает последняя корова. ФД хочет, чтобы прибывающие коровы не ждали в аэропорту слишком долго. Каково наименьшее значение максимального времени ожидания из всех коров, если ФД оптимально назначит их по автобусам. Время ожидания коровы есть разность между временем её прибытия и временем отправления автобуса, в который она распределена.

Гарантируется, что \(MC \geq N\).

ФОРМАТ ВВОДА (файл convention.in):

Первая строка содержит три разделённых одиночными пробелами целых числа \(N\), \(M\), \(C\). Следующая строка содержит \(N\) разделённых одиночными пробелами целых чисел, представляющих время прибытия каждой коровы.

ФОРМАТ ВЫВОДА (файл convention.out):

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

Бинарный поиск по ответуЖадный алгоритмИспользование сортировки
—Войти и решать
Sabotage#89938

Фермер Пауль решил саботировать доильное оборудование Фермера Джона. Доильное оборудование составляет ряд из N (3 <= N <= 100,000) доильных машин, где i-ая машина производит Mi единиц молока. ФП планирует отсоединить непрерывный блок этих машин от i-ой до j-ой (2 <= i <= j <= N-1). Заметим, что ФД не собирается отключать первую и последнюю машины, поскольку это очень заметно и легко обнаружить. Цель ФП – минимизировать среднее производство молока оставшимися машинами.
Пожалуйста, помогите ФД определить минимальное среднее значение производства молока оставшимися машинами в случае оптимальных действий ФП.
PROBLEM NAME: sabotage
Формат входных данных
* Строки 1: Целое число N.
* Строки 2..1+N: Строка i+1 содержит Mi.
Формат выходных данных
* Строка 1: Минимально возможное среднее, которого может достичь ФП, округлённое до 3 цифр после десятичной точки и с выводом 3 цифр после десятичной точки.
Примечание
Оптимальное решение – удалить машины 7 т 8 оставив 5 1 2, среднее которых равно 8/3.

Бинарный поиск по ответу
—Войти и решать
Поделиться
Класснуть