графы

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

Farmland может состоять из множества ферм. Пусть имеется \(K\) ферм. Беси хочет сделать гоночный цикл, соединив \(K\) ферм добавлением \(K\) дорожек с длиной \(X\). Каждую ферму необходимо посетить ровно раз и пройти как минимум по одной дороге каждой фермы.

Для того, чтобы сделать трассу более интересной для гонщиков, общая длина трассы должна быть не менее \(Y\). Беси хочет узнать длины всех подходящих под эти ограничения трасс. Трасса считается отличающейся от другой, если есть два соседних луга (после добавления дорожек между фермами) в одной трассе, которые не являются соседними в другой. Заметим, что имеют значение только выбранные дорожки, а не направление движения по этим дорожкам.

Они решили, что Беси будет мыть посуду со средством, а Эльза - полоскать. Беси получила поднос грязных тарелок пронумерованных от \(1\) до \(N\) (\(1 \leq N \leq 10^5\)). Эльза получил пустой поднос, куда она должна выкладывать чистые тарелки. Между Беси и Эльзой имеется поднос тарелок помытых со средством.

На каждом шагу происходит одно из следующих событий

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

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

\(M\) друзей ФД (\(1 \leq M \leq 10^5\)) часто посещают его фермы. Во время визита друга \(i\), ФД идёт с эти другом по уникальному маршруту от фермы \(A_i\) до фермы \(B_i\) (возможен случай, когда \(A_i = B_i\)). Дополнительно они могут попробовать некоторое количество молока вдоль пути, по которому они идут. Поскольку большинство друзей ФД сами фермеры, у них есть сильные предпочтения по молоку. Некоторые из его друзей пьют молоко только коров Guernsey, а оставшиеся пьют только молоко Holstein. Любой из друзей ФД будет счастлив только если он сможет попить предпочитаемое молоко во время визита.

Определите, каждый ли друг останется счастлив после визита.

\(M\) друзей ФД (\(1 \leq M \leq 10^5\)) часто его посещают. Во время визита друга \(i\), ФД вместе с ним путешествует по уникальному пути от фермы \(A_i\) до фермы \(B_i\) (возможно \(A_i = B_i\)). Дополнительно, они пробуют молоко каждой коровы на своём пути. Поскольку друзья ФД также фермеры, они имеют сильное предпочтение по молоку. Каждый из них пьёт молоко только определённого типа коров. Любой из друзей ФД будет счастливым, только если сможет попить свой предпочитаемый тип молока во время пути.

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

Игра Moo происходит на решётке из \(N \times N\) квадратных ячеек, в которые коровы вписывают свой ID (числовой).

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

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

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

ФД сделал \(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\)).

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

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

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

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

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

Следующая диаграмма помогает иллюстрировать отношения, описанные выше. Заметим, что некоторые из них Вы не рассматриваете, например "niece" (дочь сестры), поскольку если Беси "niece" для Эльзы, то Эльза "aunt" для Беси.

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

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

ФД теперь хочет выбрать такое значение величины \(K\), чтобы при просмотре видео предлагались к просмотру как релевантные как минимум ещё \(K\) видео. Однако он боится, что большое \(K\) снизит надои. Поэтому он просит Вас ответить на вопросы по поводу \(K\).

Но в тот момент, когда Беси приземляется, закон сможет определить ее местоположение. Некоторые фермеры начнут в различных выходных амбарах и попытаются поймать Беси. Фермеры двигаются на той же скорости, что и Беси (поэтому в каждый момент времени каждый фермер может перейти из своего амбара в соседний). Фермеры всё время знают, где находится Беси, и Беси всё время знает, где находятся фермеры. Фермеры поймают Беси, если в некоторый момент времени, один из фермеров находится в том же амбаре, что и Беси или проходит по тому же туннелю, что и Беси. Беси сбежит, если достигнет амбара с выходом, прежде чем любой из фермеров поймает её.

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

Заметим время на тест в этой задаче больше чем по умолчанию: 4 секунды для C/C++/Pascal, и 8 секунд для Java/Python.

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

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

ФД теперь хочет выбрать такое значение величины \(K\), чтобы при просмотре видео предлагались к просмотру как релевантные как минимум ещё \(K\) видео. Однако он боится, что большое \(K\) снизит надои. Поэтому он просит Вас ответить на вопросы по поводу \(K\).

Но в тот момент, когда Беси приземляется, закон сможет определить ее местоположение. Некоторые фермеры начнут в различных выходных амбарах и попытаются поймать Беси. Фермеры двигаются на той же скорости, что и Беси (поэтому в каждый момент времени каждый фермер может перейти из своего амбара в соседний). Фермеры всё время знают, где находится Беси, и Беси всё время знает, где находятся фермеры. Фермеры поймают Беси, если в некоторый момент времени, один из фермеров находится в том же амбаре, что и Беси или проходит по тому же туннелю, что и Беси. Беси сбежит, если достигнет амбара с выходом, прежде чем любой из фермеров поймает её.

Беси не уверена в своих шансах на успех, которые зависят от количества фермеров, которые будут за ней охотиться. Если Вам дан номер амбара \(K\), в котором приземлится Беси, определите минимальное количество фермеров, которое необходимо, чтобы поймать Беси, в предположении, что фермеры распределяться оптимально среди выходных амбаров.

bessie/
  folder1/
    file1
    folder2/
      file2
  folder3/
    file3
  file4

Самая верхняя директория называется bessie

Беси может заходить в любую директорию, какую захочет. Из данной директории любой файл может быть доступен по "относительному пути". В относительном пути символ ".." означает родительскую директорию. Например, если Беси находится в директории folder2, то она может обращаться к своим четырём файлам следующим образом:

../file1
file2
../../folder3/file3
../../file4

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

В начале тренировки ФД бросает несколько мячей различных коровам. Когда корова \(i\) получает мяч, от ФД или от другой коровы, она передаёт мяч ближайшей к ней корове. Если таких коров несколько, то она передаёт мяч самой левой из них. ФД хочет обеспечить, чтобы каждая корова хоть один раз получила мяч. Помогите ФД определить минимальное количество мячей, которое он должен бросить изначально, (правильному подмножеству коров), чтобы каждая корова хоть один раз получила мяч.

Им было здорово вместе, но настало время расставаться, уезжая по одной. Они хотят уезжать в таком порядке, чтоб пока остаётся не меньше двух коров, каждая корова имела друга среди оставшихся коров. Более того, имеется \(M\) пар коров \((a_i, b_i)\) таких, что корова \(a_i\) должна уезжать до коровы \(b_i\). Заметим, что коровы \(a_i\) и \(b_i\) могут быть, а могут и не быть друзьями.

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

ФД выбрал танец "Bovine Shuffle", в котором \(N\) коров (\(1 \leq N \leq 100,000\)) выстроены в ряд в некотором порядке, затем они выполняют успешную перестановку, которая потенциально может переупорядочить коров. ФД пометил позиции коров \(1 \ldots N\), так, что первая корова в ряду стоит на позиции 1, вторая - на позиции 2, и т.д., до позиции \(N\).

Перестановка описывается \(N\) числами, \(a_1 \ldots a_N\), означающими, что корова с позиции i переместится в позицию \(a_i\) (все \(a_i\) в интервале $1 \ldots N) Каждая корова во время перестановки идёт на свою новую позицию. К несчастью, все \(a_i\)' не обязательно различные, поэтому несколько коров могут во время перестановки придти в одну и ту же позицию. После чего они будут ходить вместе все оставшиеся перестановки.

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

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

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

Определённая ячейка решётки указана как цель. Беси должна доставить ящик в это место.

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

Замечание: в этой задаче можно использовать 512 Мбт оперативной памяти, в отличие от лимита по умолчанию в 256 Мбт.

Коровы ФН выстроились перед ФД так, что корова \(1\) в голове очереди, а корова \(N\) - в её хвосте. ФД рассчитывал, что в каждый момент времени, корова из головы очереди получит подарок и станет в конец очереди. Однако неожиданно он обнаружил, что коровы ФН ведут себя не так. После получения подарка каждая корова может пойти не в конец очереди, а вставиться перед группой коров в конце очереди. А именно корова \(i\) всегда становится точно перед \(c_i\) коровами от конца (\(0 \leq c_i \leq N-1\)).

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

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

Беси хочет отдать один из своих пирогов Эльзе. Если Эльза получит пирог от Беси, она должна будет отдать один из своих пирогов Беси. Чтобы не оказаться ни скупой, ни щедрой, Эльза постарается выбрать пирог, как минимум, такой же вкусный (по мнению Эльзы) как она получила, но не более чем на \(D\) единиц вкуснее (\(0 \leq D \leq 10^9\)). Такой пирог может не существовать, в этом случае Эльза сбежит в Японию.

Но если Эльза отдаст Беси пирог взамен, то Беси аналогично постарается отдать Эльзе пирог, как минимум такой же вкусный (по мнению Беси), но не более чем на \(D\) единиц вкуснее, чем кусок, который она получила. Если Беси не сможет, то тоже сбежит. Иначе отдаст кусок Эльзе. Этот цикл продолжается, пока возможно, или пока одна из коров не получит кусок с величиной вкусности равной \(0\), в этом случае процесс заканчивается и обе коровы счастливы.

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

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

Ферма состоит из \(N\) амбаров, соединённых \(M\) двунаправленными дорожками между некоторыми парами амбаров (\(1 \leq N, M \leq 3000\)). ФД закрывает один амбар за раз. После того как амбар закрыт, все дорожки, прилегающие к нему тоже становятся закрытыми и не могут больше использоваться.

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