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

Медиана объединений#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—Войти и решать

Эпизод 11. Сигнатура BD#94346

СЕКРЕТНО

Дело VOIDLINKER · Эпизод 11 из 13

Сигнатура BD

ИСТОЧНИК: обратный анализ backdoor v2.6

ИЗ ПЕРЕХВАЧЕННОЙ ПЕРЕПИСКИ:

«Сигнатура моего бэкдора — пара байт BD. В одном ядре их не менее 200. Найди самый короткий непрерывный участок с 200+ парами BD. Я делаю код плотным, а не водянистым. — V.»

ФОРМАЛЬНАЯ ЗАДАЧА

Текстовый файл состоит из заглавных букв A,B,C,D,E,F. Определите минимальное количество идущих подряд символов, среди которых пара BD (B и сразу за ним D) встречается не менее 200 раз. Если такой последовательности нет — выведите 0.

ВХОДНЫЕ ДАННЫЕ

Одна строка до 10⁵ символов.

ВЫХОДНЫЕ ДАННЫЕ

Одно целое число.

"Два указателя"

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

Эпизод 6. Двойная сигнатура#94341

СЕКРЕТНО

Дело VOIDLINKER · Эпизод 6 из 13

Двойная сигнатура

ИСТОЧНИК: readme.md в дампе malware

ИЗ ПЕРЕХВАЧЕННОЙ ПЕРЕПИСКИ:

«Сигнатура моего малвара двойная, для понта. Подстрока 2026 (год моего расцвета) появляется не менее 75 раз, и буква X — ровно 90 раз. Оба условия в одном непрерывном куске — и это мой модуль. Найди самый длинный. — V.»

ФОРМАЛЬНАЯ ЗАДАЧА

Определите максимальное количество идущих подряд символов, среди которых подстрока 2026 встречается не менее 75 раз и при этом содержится ровно 90 букв X. Если такого окна нет — выведите 0.

ВХОДНЫЕ ДАННЫЕ

Одна строка длиной до 3,5·10⁵ символов.

ВЫХОДНЫЕ ДАННЫЕ

Одно целое число.

"Два указателя"

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

Эпизод 4. Шифроблок Voidlinker#94339

СЕКРЕТНО

Дело VOIDLINKER · Эпизод 4 из 13

Шифроблок

ИСТОЧНИК: darknet.onion / #incident-leak / 31.10.2026 14:09

ИЗ ПЕРЕХВАЧЕННОЙ ПЕРЕПИСКИ:

«Слушай, я придумал красивый шифр. Каждый блок данных обёрнут синхросигналом — цифра 7, и в каждом валидном блоке она встречается ровно 60 раз. Не больше, не меньше. Между блоками — мусор. Найди в дампе самый длинный непрерывный участок с ровно 60 семёрками — это мой самый объёмный шифроблок. — V.»

ФОРМАЛЬНАЯ ЗАДАЧА

Текстовый файл состоит из десятичных цифр и заглавных букв латинского алфавита. Определите максимальное количество идущих подряд символов, среди которых цифра 7 встречается ровно 60 раз. Если такой последовательности нет — выведите 0.

ВХОДНЫЕ ДАННЫЕ

Одна строка длиной до 2·10⁵ символов.

ВЫХОДНЫЕ ДАННЫЕ

Одно целое число — длина найденной последовательности.

"Два указателя"

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

Повторы слов в сочинении#93159

Учительница литературы просит помечать тавтологии — когда одно и то же слово стоит подряд два раза: «был был», «очень очень».

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

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

Произвольный текст до 10 000 символов, возможно в несколько строк. Слово — это последовательность букв (кириллица или латиница), цифр и подчёркиваний.

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

Тот же текст, но каждое повторение подряд двух одинаковых слов обёрнуто в квадратные скобки: [слово слово]. Пунктуация и все остальные символы сохраняются.

Примечание

Регистр при сравнении слов не учитывается: Очень очень — тоже повтор. В выводе регистр оригинала сохраняется.

Поиск подстроки в строке

✓ 1✗ 10—Войти и решать

Даты в дневнике тренировок#93158

В заметках на телефоне ты ведёшь дневник тренировок. Даты писали по-разному: 17.04.2026, 17/04/2026, 17-04-2026, 17 апреля 2026.

Приведи все найденные даты к ISO-формату YYYY-MM-DD.

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

Произвольный текст до 10 000 символов, возможно в несколько строк. Формат даты: день (1–2 цифры), разделитель (., /, - или пробел), месяц (2 цифры или слово на русском), разделитель, год (4 цифры).

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

Каждая найденная дата в формате YYYY-MM-DD на отдельной строке в порядке появления.

Примечание

Поддерживаются названия всех 12 месяцев: январь, февраль, ..., декабрь в любой форме (январь, января, январём — достаточно, чтобы начало совпало с основой).

Поиск подстроки в строке

✓ 2✗ 1—Войти и решать

Выписка из электронного дневника#93156

Мама выгрузила из электронного дневника текстовую выписку. Каждая строка выглядит так: название предмета, двоеточие, оценки через запятую или пробел.

Напиши программу, которая для каждого предмета посчитает средний балл.

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

Одна или несколько строк вида Название предмета: оценки. Название предмета — одно или несколько русских слов (только буквы и пробелы). Оценки — целые числа от 2 до 5, разделённые запятыми и/или пробелами.

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

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

Примечание

Используй округление Python по умолчанию (функция round). Предметы без оценок (если такие попадутся) в выводе пропускай.

Поиск подстроки в строке

✓ 2✗ 3—Войти и решать

Упоминания в чате 10А#93155

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

Никнейм — это символ @, за которым идут от 5 до 32 символов: латинские буквы, цифры и подчёркивания. Короткие последовательности (меньше 5 символов) никнеймами не считаются.

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

В первой строке — число $N$ ($1 \le N \le 100$) — сколько самых упоминаемых никнеймов нужно вывести.
Далее — произвольный текст чата до 10 000 символов.

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

Топ-$N$ никнеймов в нижнем регистре, каждый на отдельной строке. Порядок — по убыванию частоты упоминаний; при равенстве частот раньше идёт тот, кто первым встретился в тексте.

Если уникальных никнеймов меньше $N$, выведи все, что есть.

Примечание

Регистр при подсчёте игнорируется: @Katya и @katya — один человек.

Поиск подстроки в строке

✓ 2✗ 9—Войти и решать

Хештеги в посте ВК#93151

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

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

Хештег — это символ #, за которым идут один или более символов: буквы (латиница или кириллица), цифры или подчёркивания.

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

Произвольный текст от одной до 100 строк, общей длиной не более 10 000 символов.

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

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

Поиск подстроки в строке

✓ 11✗ 10—Войти и решать

Regex-Quest. 2. Письма из ниоткуда#92507

📧

Шаг 2: Письма из ниоткуда

Просто

День второй. На почту приёмной комиссии завалилось 347 писем от абитуриентов. Кто-то пишет email в подписи, кто-то в теле письма, кто-то прямо в теме: «Если что, пишите на vasya.gamer@hse.ru, я там всегда онлайн». Твой начальник просит собрать все email в один список, потому что Excel у него снова завис. Печаль.

Условие задачи

Email считается валидным, если он состоит из:

имени из латинских букв, цифр и точек,
символа @,
домена из латинских букв, цифр и точек,
точки и доменного зона из 2–4 латинских букв (например, .ru, .edu, .com).

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

Одна строка произвольного текста.

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

Все найденные email-адреса, по одному на строке, в порядке появления.

Подсказка: Шаблон: [a-zA-Z0-9.]+@[a-zA-Z0-9.]+\.[a-zA-Z]{2,4}. Не забудь экранировать точку перед доменной зоной: \..

Поиск подстроки в строке Строки

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

Censoring (Bronze)#90403

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

ФД взял текст из журнала и создал строку S длиной не более чем 10^6 символов. Из неё он хочет удалить все вхождения подстроки T длиной <= 100 символов неподходящего содержания. Чтобы сделать это, ФД ищет первое вхождение T в S и удаляет его. Затем он повторяет процесс опять, снова удаляя первое вхождение T, продолжая так до тех пор, пока больше не станет вхождений T в S. Заметим, что удаление одного вхождения может создать другое вхождение, которое не существовало раньше.

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

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

Первая строка содержит S. Вторая строка будет содержать T. Длина T не более чем длина S, и все символы S и T - маленькие латинские буквы (a..z).

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

Строка S после завершения всех удалений. Гарантируется, что S не станет пустой после завершения процесса всех удалений.

Поиск подстроки в строке реализация Стек

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

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—Войти и решать