Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Медиана объединений#56019

Дано N упорядоченных по неубыванию последовательностей целых чисел (т.е. каждый следующий элемент больше либо равен предыдущему), в каждой из последовательностей ровно L элементов. Для каждых двух последовательностей выполняют следующую операцию: объединяют их элементы (в объединенной последовательности каждое число будет идти столько раз, сколько раз оно встречалось суммарно в объединяемых последовательностях), упорядочивают их по неубыванию и смотрят, какой элемент в этой последовательности из 2L элементов окажется на месте номер L (этот элемент называют левой медианой).

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

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

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

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

Выходные данные
В первой строке выведите медиану объединения 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 строках задаются параметры, определяющие последовательности.

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

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

Выходные данные
В первой строке выведите медиану объединения 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—Войти и решать

То березка, то рябина…#38572

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

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

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

Входные данные
В первой строке вводятся два целых числа: K — количество различных видов деревьев (1 ≤ K ≤ 100 000), и P — требуемое количество подряд идущих деревьев разных видов (2 ≤ P ≤ K). Последующие K строк входных данных содержат целые числа ai, задающие количество закупленных саженцев деревьев i-го вида (1 ≤ a_i ≤ 10⁹), по одному числу в каждой строке.

Выходные данные
Выведите единственное число — максимальное количество деревьев, посадка которых в ряд в некотором порядке достигает эстетического совершенства.

Примеры

№	Входные данные	Выходные данные
1	3 3 1 200 1	4

Бинарный поиск в массиве Бинарный поиск по ответу Жадный алгоритм

✓ 3✗ 171 300средняяВойти и решать

Agar.io#38466

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

Формат входных данных
Программа получает на вход целое число n, 1 ≤ n ≤ 10⁵ — количество игроков. Следующие n строк содержат по одному числу a_i — размеры бактерий, 1 ≤ a_i ≤ 10⁹. Числа a_i заданы в порядке неубывания.
Формат выходных данных
Программа должна вывести n чисел равных «0» или «1», по одному числу в строке. Если i-е число равно 0, то это означает, что i-й игрок (размер бактерии которого первоначально был равен
a_i) ни при каких обстоятельствах не может выиграть в этой игре. Если i-е число равно 1, то это означает, что i-й игрок имеет возможность выиграть в этой игре.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 1 1 3 4	0 0 1 1	В примере из условия 4 бактерии размерами 1, 1, 3, 4. Бактерии размером 1 никого не могут съесть, поэтому не могут выиграть. Бактерия размером 4 может съесть всех. Бактерия размером 3 может съесть по очереди две бактерии размером 1. Тогда её размер станет 5, после этого она сможет съесть бактерию размером 4 и выиграть. Ответ: 0, 0, 1, 1.

Бинарный поиск Бинарный поиск по ответу

✓ 68✗ 266900средняяВойти и решать

Сложность двоичного поиска#33009

Вася загадал число от 1 до N. За какое наименьшее количество вопросов (на которые Вася отвечает "да" или "нет") Петя может угадать Васино число?

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

Вводится одно число N

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

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

Ввод	Вывод
5	3

Бинарный поиск Бинарный поиск в массиве

✓ 366✗ 540400лёгкаяВойти и решать

Квадратный корень и квадратный квадрат#27292

Найдите такое число x, что $x^2 + \sqrt{x} = C$ , с точностью не менее 6 знаков после точки.

Входные данные
В единственной строке содержится вещественное число $1 <=C <=10^{10}$.

Выходные данные
Выведите одно число — искомый $x$.

Примеры

№	Входные данные	Выходные данные
1	2.0000000000	1.000000000
2	18.0000000000	4.000000000

Бинарный поиск значения функции Бинарный поиск по ответу

✓ 415✗ 467500лёгкаяВойти и решать

Кубическое уравнение#27291

Даны четыре действительных числа: A, B, C, D. Найдите все корни уравнения Ax³+Bx²+Cx+D=0. Известно, что все корни этого уравнения не превосходят по абсолютной величине 1000. Известно, что любые два корня этого уравнения различаются не менее, чем на 10^-6.

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

Программа получает на вход четыре действительных числа: A, B, C, D. Любые из этих четырех чисел, но не все одновременно, могут быть равны 0.

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

Программа должна вывести от 0 до 3 действительных чисел: корни данного уравнения в порядке возрастания. Кратные корни должны быть выведены только один раз. Значения корней необходимо выводить с точностью до 6 знаков после точки.

Ввод	Вывод
0 0 1000 -1	0.001

Бинарный поиск значения функции Бинарный поиск по ответу

✓ 30✗ 3381 000средняяВойти и решать

Приближенный двоичный поиск#27279

Реализуйте алгоритм приближенного бинарного поиска.

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

В первой строке входных данных содержатся числа N и K ($0< N,\ K <100001$). Во второй строке задаются N чисел первого массива, отсортированного по неубыванию. В третьей строке вводится K чисел второго массива.
Каждое число в обоих массивах по модулю не превосходит $2 \cdot 10^9$.

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

Бинарный поиск Бинарный поиск в массиве

✓ 793✗ 2 039600лёгкаяВойти и решать

Совсем другие штурмовики#23366

Вы управляете армией штурмовиков, сражающейся против армии повстанцев. Армия повстанцев состоит из n солдат, здоровье i-го солдата составляет ai единиц. Сила атаки каждого вражеского солдата равна de единиц. В Вашем распоряжении есть m штурмовиков. Сила атаки каждого из них — d_t, здоровье — h единиц.

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

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

Формат входных данных
В первой строке входного файла заданы натуральные числа n, m, ( n,m <= 2*10⁵), d_e, d_t , h — число солдат в армии противника, число штурмовиков в вашем распоряжении, сила атаки каждого солдата неприятеля, сила атаки и число единиц здоровья каждого из штурмовиков соответственно ( d_e, d_t , h <= 10⁹). В следующей строке задано n натуральных чисел a_i — число единиц здоровья i-го солдата армии противника (a_i <= 10⁹).
Формат выходных данных
Выведите единственное число — минимальное количество штурмовиков, необходимое для уни чтожения армии противника, либо -1, если миссия невыполнима.

Ввод	Вывод
3 3 1 1 2 1 2 3	3
4 10 2 1 2 1 2 1 2	5
3 1 1 2 5 1 2 3	-1

Бинарный поиск Бинарный поиск по ответу

✓ 1✗ 31 200средняяВойти и решать

Зелье от морской болезни#91198

Шкипер Баг ужасно страдает от морской болезни. Единственное спасение — зелье «Штиль», которое продаётся в лавках на островах архипелага. На n островах цены разные: в i-м порту бутылка стоит xi дублонов.

Каждый раз, когда «Нулевой указатель» заходит в порт, у Шкипера Бага с собой разная сумма — зависит от того, не украл ли корабельный кот монеты из кармана. Всего таких заходов будет q. Для каждого захода Шкипер Баг хочет заранее знать: в скольких портах архипелага он смог бы купить зелье, имея столько дублонов?

Формат входных данных
Первая строка: n (1≤n≤100 000) — количество портов.
Вторая строка: n чисел xi (1≤xi≤100 000) — цены на зелье.
Третья строка: q (1≤q≤100 000) — количество заходов в порт.
Следующие q строк: число mi (1≤mi≤10⁹) — дублоны Шкипера Бага при i-м заходе.

Формат выходных данных
q чисел — для каждого захода количество портов, где хватит денег.

Примечание:
При 1 дублоне ни одна лавка недоступна. При 8 — можно купить в 4 лавках (цены 2, 3, 4, 7). При 3 — только одна лавка (цена 2). При 100 дублонах — все пять.

*1100 Бинарный поиск дп реализация

✓ 4✗ 381 100средняяВойти и решать

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$. А затем повторяет следующую процедуру каждый день:

Предположим, что ФД уже отдал Беси $G$ галлонов молока, он вычисляет $\frac{N-G}{X}$ с округлением вверх. Назовём это число $Y$.
Если $Y$ меньше чем $M$, то устанавливает $Y$ равным $M$.
Даёт Беси $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$, содержащую порядок в котором ФД должен доить своих коров.

Бинарный поиск по ответу графы Топологическая сортировка

—Войти и решать