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

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\), содержащую порядок в котором ФД должен доить своих коров.

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

Milking Order#90025

\(N\) коров (\(2 \leq N \leq 100\)) Фермера Джона, последовательно пронумерованных \(1 \ldots N\) разработали структуру утреннего доения. Она основывается на двух ключевых свойствах:

1. Некоторые коровы настаивают чтобы их доили раньше - в соответствии с их социальным статусом. Например, корова 3 имеет наивысший статус, корова 3 имеет средний статус, а корова 5 имеет низкий статус, то корову 3 нужно доить первой, затем корову 2 и затем корову 5.

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

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

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

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

Первая строка содержит \(N\), \(M\) (\(1 \leq M < N\)), \(K\) (\(1 \leq K < N\)), указывающая, что у ФД \(N\) коров, \(M\) из которых организованы в социальную иерархию, \(K\) из которых требуют, чтобы их подоили в определённой позиции порядка. Следующая строка содержит \(M\) различных целых чисел \(m_i\) (\(1 \leq m_i \leq N\)). Коровы, представленные в этой строке должны доиться в порядке, в котором они появились в этой строке. Следующие \(K\) строк содержат по по два целых числа \(c_i\) (\(1 \leq c_i \leq N\)) и \(p_i\) (\(1 \leq p_i \leq N\)), указывающих, что корова \(c_i\) должна быть подоена на позиции \(p_i\).

Гарантируется, что ФД может сконструировать порядок доения, удовлетворяющий всем условиям.

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

Выведите самую раннюю позицию, на которой можно подоить корову 1.

графы реализация Топологическая сортировка

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

Milk Scheduling#89876

N (1 <= N <= 10,000) коров Фермера Джона пронумерованы последовательно от 1 до N. Для доения коровы i требуется T(i) единиц времени. Однако некоторые коровы необходимо подоить ранее других (из-за их положения на ферме). Если корову A требуется подоить перед коровой B, ФД должен полностью закончить дойку коровы A, прежде чем начать дойку коровы B.
Для того, чтобы подоить всех своих коров как можно быстрее, ФД нанял большое количество доярок - достаточно для того чтобы доить любое количество коров одновременно.
Определите минимальное количеатво времени, требуемое для дойки всех коров.

PROBLEM NAME: msched
Формат входных данных
* Строка 1: Два разделенных пробелом целых числа: N (количество коров) и M (количество ограничений).
* Строки 2..1+N: Строка i содержит значение T(i).
* Строки 2+N..1+N+M: Каждая строка содержит два разделенных пробелом целых числа A и B, означающих, что корова A должна быть полностью подоена, прежде чем приступать к дойке коровы B.

Формат выходных данных
* Строка 1: Минимальное количество времени, требуемое чтобы подоить всех коров.
Примечание
Коров 1 и 3 можно начинать доить сразу и делать это одновременно. Когда закончится дойка коровы 3, можно начинать дойку коровы 2. Через 11 единиц времени закончится дойка всех коров.

Топологическая сортировка

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

First!#89809

Беси опять играет со строками. Она обнаружила, что изменяя порядок алфавита она може добиться, чтобы некоторая строка стала лексикографически раньше всех.
Например, среди строк
"omm", "moo", "mom", "ommnom"
она может сделать первой строку "mom", используя стандартный алфавит. и она может сделать первой строку "omm" используя алфавит "abcdefghijklonmpqrstuvwxyz". Однако Беси не знает как сделать первым слово "moo" или "ommnom"
Помогите Беси вычислить строки из ввода, которые можно сделать первыми изменив порядок букв в алфавите.
Чтобы определить, что строка X лексикографически раньше cтроки Y найдите индекс первого символа в котором они различаются j. Если такого индекса нет, тогда X лексикографически меньше чем Y, если X короче чем Y, иначе, X лексикографически раньше чем Y, если X[j] находится в алфавите раньше чем Y[j].

PROBLEM NAME: first
Формат входных данных
* Строка 1: целое N (1 <= N <= 30,000),количество строк, с которыми играет Беси
* Строки 2..1+N: Каждая строка содержит не пустую строку символов. Общее количество символов во всех строках не превысит 300,000. Все символы на вводе - маленькие латинские буквы от 'a' до 'z'. Во вводе нет повторяющихся строк.

Формат выходных данных
* Строка 1: одно число K, количество строк, которые могут быть лексикографически первыми.
* Строки 2..1+K: (1+i)-ая строка должна содержать i-ую строку, которая может быть лексикографически первой. Строки нужны выводить в том же порядке, в котором они следовали на вводе.
Примечание
Только "omm" и "mom" могут стать первыми.

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

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

Топологическая сортировка#68537

Задан ориентированный ациклический граф с \(n\) вершинами и \(m\) ребрами. Также задана перестановка вершин графа. Необходимо проверить, является ли данная перестановка топологической сортировкой.

В первой строке даны два числа \(n\) и \(m\) — количество вершин и ребер в графе соответственно (\(1 \leq n, m \leq 10^5\)). В следующих \(m\) строках заданы пары чисел \(u_i, v_i\), означающие, что в графе есть ребро из вершины \(u_i\) в вершину \(v_i\). В последней строке задана перестановка из \(n\) элементов.

Выведите "YES" (без кавычек), если данная перестановка является топологической сортировкой и "NO" в противном случае.

Применение обхода в глубину Топологическая сортировка

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

Магистраль "Урал"#51109

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

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

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

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

Формат входных данных
Первая строка входного файла содержит целое число \(n\) "— количество пластов. Пласты пронумерованы целыми числами от \(1\) до \(n\) в произвольном порядке.

В \(i\)-й из следующих \(n\) строк содержатся целые числа \(l_i\) и \(r_i\) (\(0 \leqslant l_i < r_i\leqslant 10^9\)) "— расстояния от начала магистрали до точек, под которыми начинается и заканчивается \(i\)-й пласт.

В следующей строке записано целое число \(m\) "— количество скважин, в которых проводилось бурение. Следующие \(m\) строк описывают результаты бурения: в каждой строке сначала указаны два целых числа \(x\) (\(0 \leqslant x \leqslant 10^9\)) и \(k\) (\(0 \leqslant k \leqslant n\)) "— расстояние от начала магистрали до скважины и количество обнаруженных в данной скважине пластов, затем "— целые числа \(s_1, s_2, \ldots, s_k\) "— номера пробуренных пластов, перечисленные в порядке залегания сверху вниз. Скважины перечислены в порядке возрастания расстояния \(x\).

Гарантируется, что решение существует.

Формат выходных данных
Первая строка выходного файла должна содержать \(n\) целых чисел \(p_1, p_2, \ldots , p_n\), описывающих возможный порядок залегания пластов сверху вниз. Среди чисел \(p_1, p_2, \ldots , p_n\) каждый номер пласта должен встретиться ровно один раз. При этом пласт с номером \(p_j\) не должен нигде проходить выше пластов с номерами \(p_1, \ldots ,p_{j-1}\) или ниже пластов с номерами \(p_{j+1}, \ldots , p_n\).

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

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

графы Дерево отрезков, RSQ, RMQ Топологическая сортировка

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

Построение#38569

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

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

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

Входные данные
Сначала на вход программы поступают числа N и M (1 < N <= 100, 1 <= M <= 5000) – количество солдат в роте и количество пар солдат, про которых прапорщик знает, кто из них выше. Далее идут эти пары чисел A и B по одной на строке (1 <= A,B <= N), что означает, что, по мнению прапорщика, солдат A выше, чем B. Не гарантируется, что все пары чисел во входных данных различны.

Выходные данные
В первой строке выведите "Yes" (если можно построиться так, чтобы прапорщик остался доволен) или "No" (если нет). После ответа "Yes" на следующей строке выведите N чисел, разделенных пробелами, - одно из возможных построений.

Примеры

№	Входные данные	Выходные данные
1	4 5 1 2 2 3 3 4 1 4 4 1	No

Обход в глубину Топологическая сортировка

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

*Производство деталей#34975

Предприятие «Авто-2010» выпускает двигатели для известных во всём мире автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n, при этом деталь с номером i изготавливается за pi секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.

Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить её на выставке.

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

Входные данные
Первая строка входного файла содержит число n (1≤ n ≤ 100000) — количество деталей двигателя. Вторая строка содержит n натуральных чисел p₁, p₂, p_n, определяющих время изготовления каждой детали в секундах. Время для изготовления каждой детали не превосходит 10⁹ секунд.

Каждая из последующих n строк входного файла описывает характеристики производства деталей. Здесь i-я строка содержит число деталей ki, которые требуются для производства детали с номером i, а также их номера. В i-й строке нет повторяющихся номеров деталей. Сумма всех чисел k_i не превосходит 200000.

Известно, что не существует циклических зависимостей в производстве деталей.

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

Ввод	Вывод
3 100 200 300 1 2 0 2 2 1	300 2 2 1
2 2 3 1 2 0	5 2 2 1
4 2 3 4 5 2 3 2 1 3 0 2 1 3	9 3 3 2 1

Обход в глубину Топологическая сортировка

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

*Упорядочивания#33257

Сегодня у Кэрол выходной. Но даже в этот прекрасный весенний день она не отдыхает, а тренируется и готовится к сражениям со скруллами. Одним из важных навыков является умение быстро ориентироваться в незнакомых местах. Для того, чтобы отточить это умение, Кэрол пригласила своего наставника Йон-Рогга.

Кэрол и Йон-Рогг будут играть в следующую игру. Сначала Йон-Рогг нарисует на бумаге карту убежища скруллов. Карта представляет из себя n помещений, пронумерованных от 1 до n. Некоторые пары помещений соединены двусторонними переходами. Убежище устроено так, что от любого помещения до любого другого можно добраться, перемещаясь по коридорам. Для того, чтобы игра не была слишком сложной, Йон-Рогг нарисует ровно n − 1 переход между помещениями. Иными словами, карта убежища представляет собой дерево.

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

После того, как Йон-Рогг нарисует на бумаге карту убежища, он также для каждого перехода отметит, в каком направлении по нему перемещаются роботы. Иными словами, Йон-Рогг ориентирует ребра нарисованного дерева.

Чтобы структурировать карту убежища, Кэрол должна составить список, состоящий из всех номеров помещений в некотором порядке. При этом должно выполняться следующее условие: в любом переходе роботы перемещаются от помещения, которое идет в списке раньше, к помещению, которое идет с писке позже. Более формально, Кэрол должна составить такую перестановку номеров помещений p₁p₂ . . . p_n, для которой верно, что если роботы могут перемещаться по переходу от помещения pi к помещению p_j , то i < j.

Пока Кэрол бьется над своим заданием, Йон-Роггу стало интересно, сколько всего решений существует у этой задачи. Иными словами, Йон-Роггу интересно, сколько перестановок удовлетворяют условию, описанному выше. Помогите ему узнать это. Так как ответ может быть очень большим, Йон-Рогг попросил вас сообщить лишь его остаток от деления на 998 244 353.

Входные данные: Первая строка входных данных содержит единственное целое число n — количество помещений в убежище, нарисованном Йон-Роггом (1 <= n <= 3 000).

Каждая из следующих n − 1 строк содержит два целых числа a, b — номера помещений, соединенных очередным коридором (1 <= a, b <= n). Роботы перемещаются по коридору в направлении от помещения a к помещению b.

Гарантируется, что убежище представляет собой дерево, то есть от любого помещения можно добраться до любого другого, двигаясь по переходам (возможно, в направлении, противоположном направлению движения роботов в этом переходе).

Выходные данные: Выведите остаток от деления на 998 244 353 количества различных перестановок p₁p₂ . . . p_n, для которых верно, что если роботы перемещаются по переходу от помещения p_i к помещению p_j , то i < j.

Примеры

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

Замечание

В первом тесте из примера Кэрол может выписать две перестановки: {1, 2, 3} или {1, 3, 2}.

Во втором тесте Кэрол может выписать три перестановки: {2, 3, 1, 4}, {2, 3, 4, 1} или {2, 4, 3, 1}.

Топологическая сортировка

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

Количество способов топологической сортировки#29453

Дан связный ациклический ориентированный граф. Каждая вершина данного графа кроме листьев имеет по 2 сына.

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

Входные данные
Входная строка содержит одно натуральное число n - кол-во вершин (n <= 1000).

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

Примеры

№	Входные данные	Выходные данные
1	7	48

Топологическая сортировка

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

Лексикографически минимальная топологическая сортировка#29452

Дан связный ациклический ориентированный граф. Найдите его лексикографически минимальную топологическую сортировку.

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

В первой строке вводится количество вершин n (1 <= n <= 10000). Во второй строке водится n чисел a_i (0 <= a_i <= n, a_i != i). Значение a_i - предок вершины с номером i (вершины нумеруются с 1). Если a_i = 0, то вершина i является корнем и не имеет предков, гарантируется, что таких вершин ровно 1.

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

Решение должно вывести n чисел - лексикографически минимальную топологическую сортировку.

Примеры

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

Топологическая сортировка

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

Расписание для 9И#29451

В августе Владлена Александровна решила составить расписание для 9 «И» класса. Она считает, что уроков в один день должно быть N (2<=N<=8). От учителей она получила M (1<=N) запросов. Так как Владлена Александровна учитель географии, то с компьютером опыт работы у нее не такой как у вас, она просит вас о помощи, решите эту «невыполнимую» задачу, соблюдая запросы учителей.

Входные данные: В первой строке входных данных содержится число N – кол-во уроков и число M – количество последовательных пар уроков наверное.

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

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

Слова, которые можно вводить: PE,Math, Russian, Biology,Geometry, Literature, Science, Geography

Выходные данные: Задача — выстроить предметы в подходящем для всех пар порядке.

Ввод	Вывод
3 2 PE Math Math Literature	PE Math Literature

Топологическая сортировка

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

Спасти новобранцев#29450

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

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

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

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

Сначала на вход программы поступают числа N и M (1 < N <= 100, 1 <= M <= 5000) – количество солдат в роте и количество пар солдат, про которых прапорщик знает, кто из них выше. Далее идут эти пары чисел A и B по одной на строке (1 <= A,B <= N), что означает, что, по мнению прапорщика, солдат A выше, чем B. Не гарантируется, что все пары чисел во входных данных различны.

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

В первой строке выведите "Yes" (если можно построиться так, чтобы прапорщик остался доволен) или "No" (если нет). После ответа "Yes" на следующей строке выведите N чисел, разделенных пробелами, - одно из возможных построений.
Примеры

№	Входные данные	Выходные данные
1	4 5 1 2 2 3 3 4 1 4 4 1	No

Топологическая сортировка

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

Дороги королевства#29449

В одном королевстве n городов и m дорог. У каждого города есть своё название, состоящее из строчных латинских букв. Но королю не нравится, что есть дороги, ведущие из города с названием, являющимся лексикографически меньшим названия конечного. Он захотел это исправить, поменяв города, к которым относятся те или иные названия. Сам он, конечно, не справится. Помогите ему в этом!

Формат файла входных данных:

Первая строка содержит два целых числа n и m (2 <= n <= 1000; 1 <= M <= 10000) - количество городов и дорог в королевстве соответственно.

Вторая строка содержит n строк, описывающих города. Описание задаётся строкой из строчных латинских букв - названия города.

Далее в m строках перечислены дороги. Каждая дорога задаётся парой чисел - номерами начального и конечного городов соответственно. Дороги односторонние.

Формат файла выходных данных:

Вывести n чисел, каждое из которых обозначает номер названия, соответствующего i-ому городу. Если решения не существует, вывести -1.

Ввод	Вывод
4 4 aaa bacc cqe de 1 4 4 2 4 3 3 2	1 4 3 2
3 3 fi bru a 1 2 2 3 3 1	-1

(с) Филимонов И.

Топологическая сортировка

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

Топологическая сортировка#24753

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

Входные данные: В первой строке содержатся два натуральных числа n и m (1≤n≤10⁵, 1≤m≤10⁵) — количество вершин и рёбер в графе соответственно. Далее в m строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин соответственно (нумерация вершин начинается с 1).

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

Примеры

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

Обход в глубину Топологическая сортировка

✓ 717✗ 1 848600лёгкаяВойти и решать