кратчайшие пути

Коровы сформировали танцевальную команду, а Фермер Джон их хореограф. Последний и самый большой танец включает \(N\) коров (\(2 \le N \le 10^6\)), стоящих в ряд. Каждое движение в танце вовлекает две коровы на расстоянии до \(K\) позиций друг от друга (\(1 \le K < N\)) грациозно прыгающих и приземляющихся в каждой другой позиции.

�меется два типа коров в этом ряду Guernseys и Holsteins. Поэтому ФД задокументировал танец как последовательность двоичных строк длины \(N\) , где a \(0\) представляет Guernsey, a \(1\) представляет Holstein, и вся строка представляет как коровы расположены в ряду.

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

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

ПР�МЕР ВВОДА:

4 1
0111
1110

ПР�МЕР ВЫВОДА:

3

Один возможный танец:

0111 -> 1011 -> 1101 -> 1110

ПР�МЕР ВВОДА:

5 2
11000
00011

ПР�МЕР ВЫВОДА:

3

Один возможный танец:

11000 -> 01100 -> 00110 -> 00011

ПР�МЕР ВВОДА:

5 4
11000
00011

ПР�МЕР ВЫВОДА:

2

Один возможный танец:

11000 -> 10010 -> 00011

Problem credits: Benjamin Qi

Каждая из \(N\) коров (\(1 \leq N \leq 10^5\)) Фермера Джона любит ежедневно прогуливаться вдоль изгороди вокруг пастбища.

Изгородь состоит из \(P\) столбов (\(4 \leq P \leq 2\cdot 10^5\), \(P\) чётное), расположение каждого из них имеет координаты \((x,y)\) на карте фермы (\(0 \leq x, y \leq 1000\)). Каждый столб соединяется с двумя соседними столбами либо горизонтальным, либо вертикальным отрезком. Таким образом вся изгородь может рассматриваться как многоугольник стороны которого параллельны осям координат x или y. Последний столб соединён с первым, поэтому получается замкнутый многоугольник вокруг пастбища. Отрезки изгороди могут пересекаться только в конечных точках, каждый столб принадлежит ровно двум конечным точкам отрезков, и каждые два отрезка, которые имеют общую точку, перпендикулярны.

Каждая корова имеет предпочтительные стартовую и конечную позиции прогулки, которые являются точками где-то вдоль изгороди (возможно в столбе, возможно нет) Каждая корова совершает свою ежедневную прогулку начиная со своей стартовой позиции и заканчивая в своей конечной позиции. Имеется два маршрута, которые корова может выбрать, поскольку изгородь представляет замкнуты цикл. Поскольку коровы ленивы, каждая корова идёт вдоль изгороди в направлении, которое обеспечивает кратчайший путь из начальной точки в конечную. Если оба пути одинаковы, корова может выбрать любое направлении.

Определите расстояние, которое пройдёт каждая корова.

**Замечание: время на тест в этой задаче 3 сек, в 1.5 раза больше чем по умолчанию. Память на тест 512 Мбт, что в два раза больше чем по умолчанию.

Фермер Джон хочет продвинуть свою линию электрических тракторов, создав рекламную сеть электрозарядных станций. Он подготовил \(N\) (\(2\le N\le 5\cdot 10^4\)) интересных точек, пронумеровав их \(1\dots N\), из которых первые \(C\) (\(1\le C < N\)) это зарядные станции, а оставшиеся - станции для посещения во время рекламного путешествия. Эти интересные точки соединены (\(1\le M\le 10^5\)) двунаправленными дорогами, \(i\)-ая из которых соединяет различные точки \(u_i\) и \(v_i\) (\(1\le u_i, v_i\le N\)) и имеет длину \(\ell_i\) миль (\(1\le\ell_i\le 10^9\)).

Электротрактор может путешествовать \(2R\) миль (\(1\le R\le 10^9\)) на одной зарядке, позволяя достичь любую точку в пределах \(R\) миль от зарядной станции. Точка назначения считается хорошо-связной, если она достижима не менее чем из \(K\) (\(1\le K\le 10\)) различных зарядных станций. Ваша задача - помочь ФД определить множество хорошо связных точек назначения.

**Замечание: Время на тест в этой задаче 4s, в два раза больше чем по умолчанию. Ограничение по памяти для этой задачи 512MB, в два раза больше чем по умолчанию.**

У Фермера Джона \(N\) (\(2\le N\le 2\cdot 10^5\)) тракторов, где -ый трактор может использоваться только в интервале \([l_i,r_i]\) включительно. Интервалы для тракторов имеют левые конечные точки \(\ell_1<\ell_2<\dots<\ell_N\) и правые конечные точки \(r_1<r_2<\dots<r_N\). Некоторые из тракторов специальные.

Два трактора \(i\) и \(j\) называются соседними если \([\ell_i,r_i]\) и \([\ell_j,r_j]\) пересекаются. ФД может перебраться (выполнить трансфер) с одного трактора на любой соседний трактор. Путь между двумя тракторами \(a\) и \(b\) состоит трансферов таких, что первый трактор в последовательности есть \(a\), последний трактор в последовательности есть \(b\) и каждые два трактора в последовательности соседние. Гарантируется ,что имеется путь из трактора \(1\) в трактор \(N\). Длина пути - количество трансферов (или эквивалентно, количество тракторов минус один).

Вам даётся \(Q\) (\(1\le Q\le 2\cdot 10^5\)) запросов, каждый указывает пару тракторов \(a\) и \(b\) (\(1\le a<b\le N\)). Для каждого запроса выведите два целых числа:

• Длину любого кратчайшего пути между тракторами \(a\) и \(b\).
• Количество специальных тракторов, таких, что существует как минимум один кратчайший путь из трактора \(a\) в трактор \(b\), содержащий его.

**Замечание: Время на тест в этой задаче 4 сек, в два раза больше времени на тест по умолчанию.**

Беси на каникулах, она может путешествовать во времени, И нет проблем если две версии Беси встретятся.

В этой стране имеется \(N\) аэропортов, пронумерованных \(1, 2, \ldots, N\) и \(M\) полётов во времени (\(1\leq N, M \leq 200000\)). Полёт \(j\) вылетает из аэропорта \(c_j\) в момент времени \(r_j\), и прибывает в аэропорт \(d_j\) в момент времени \(s_j\) (\(0 \leq r_j, s_j \leq 10^9\), \(s_j < r_j\) - такое возможно!). Кроме того, она должна потратить \(a_i\) времени для пересадки в аэропорту \(i\) (\(1\le a_i\le 10^9\)). Необходимо отметить, что если Беси прилетает в аэропорт \(i\) в момент времени \(s\), она может пересесть на рейс, который отправляется в момент времени \(r\), только если \(r \geq s + a_i\).

Беси начинает в городе \(1\) в момент времени \(0\). Для каждого аэропорта от \(1\) to \(N\), каково минимальное время когда Беси сможет в него попасть?

Ферма Джона может быть представлена как ориентированный взвешенный граф, с дорогами (дугами), соединяющими различные вершины и вес каждой дуги есть время, которое требуется чтобы проехать по этой дороге. Каждый день Беси любит путешествовать из амбара (вершина \(1\)) в поле (вершина \(N\)), используя ровно \(K\) дорог и хочет добраться до поля как можно быстрее при этих ограничениях. Однако, в некоторой точке, прекращается поддержка дорог и они начинают ломаться одна за другой, становясь непроходимыми. Помогите Беси определить кратчайший путь от амбара до поля во все моменты времени.

Формально, мы начинаем с полного взвешенного ориентированного графа из \(N\) вершин (\(1\le N\le 300\)) и \(N^2\) дуг: одна дуга для каждой пары \((i, j)\) \(1 \le i, j \le N\), заметим, что имеется \(N\) петель (дуг из \(i\) в \(i\)). После каждого удаления выведите минимальный вес из всех путей из \(1\) в \(N\), проходящих ровно \(K\) (необязательно различных) дуг \(2\le K\le 8\)). Заметим, что после \(i\)-го удаленя в графе остаётся \(N^2-i\) дуг.

Вес пути определяется как сумма весов всех дуг в пути. Заметим, что путь может содержать множество вхождений одних и тех же дуг, и одних и тех же вершин, включая \(1\) и \(N\).

Сейчас Эльза создаёт новый неориентированный граф \(G\) с \(N_1\cdot N_2\cdots N_K\) вершинами, каждая из которых помечена \(K\)-плетом \((j_1,j_2,\ldots,j_K)\), где \(1\le j_i\le N_i\). В \(G\) две вершины \((j_1,j_2,\ldots,j_K)\) и \((k_1,k_2,\ldots,k_K)\) соединены ребром, если для всех i \(1\le i\le K\), \(j_i\) и \(k_i\) соединены ребром в \(G_i\).

Определим расстояние между двумя вершинами в \(G\) которые лежат в одной и той же связной компоненте как минимальное количество ребер на пути из одной вершины в другую. Вычислите сумму расстояний между вершиной \((1,1,\ldots,1)\) и каждой вершиной в этой же компоненте в \(G\) по модулю \(10^9+7\).

\(|i-j|\) минут требуется, чтобы передать сообщение от коровы \(i\) к корове \(j\). Однако не все породы готовы взаимодействовать друг с другом, что описано в матрице \(S\) размером \(K \times K\), где \(S_{ij} = 1\) если корова породы \(i\) готова передать сообщение корове породы \(j\) и 0 в противном случае. Необязательно истина то, что \(S_{ij}=S_{ji}\), и даже может быть случай, когда \(S_{ii} = 0\), то есть корова породы \(i\) не будет передавать сообщение корове своей породы.

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

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

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

Ответ на каждый запрос необходимо вывести в виде дроби \(a/b\), где \(a\) и \(b\) положительные и взаимно простые целые числа. Выведите \(-1\) если путешествие невозможно.

Ферма описывается как \(N\) полей (\(1 \leq N \leq 10,000\)), последовательно пронумерованных \(1 \ldots N\), амбар находится в поле 1. Поля соединены \(M\) двунаправленными тропинками (\(N-1 \leq M \leq 50,000\)). С каждой тропинкой ассоциировано время её прохождения, и от любого поля имеется путь к амбару, состоящий из некоторого множества тропинок.

Поле \(i\) содержит \(c_i\) коров. Услышав колокол, все коровы двигаются к амбару так, чтобы потратить минимальное количество времени. Если имеется несколько путей с минимальным временем, коровы выбирают "лексикографически минимальный" путь. Например, путь через поля 7,3,6,1 лексикографически минимальнее, чем путь 7,5,1.

ФД хочет сократить общее время движения (сумму времён движения всех коров) как можно больше добавлением одной сокращающей тропинки, которая имеет время прохождения \(T\) (\(1 \leq T \leq 10,000\)), от амбара (поле 1) до другого поля, которое он выберет. Если корова встретится с этой сокращающей тропинкой на своём обычном пути, тогда корова пойдёт по этой тропинке, если в результате уменьшится время её прихода в амбар. Иначе, корова пойдёт по своему обычному маршруту, даже если бы она могла уменьшить своё время в пути, используя сокращающую тропинку.

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

Сеть труб описывается \(N\) точками соединения (конечными точками труб), последовательно пронумерованных \(1 \ldots N\) (\(2 \leq N \leq 1000\)). Точка соединения 1 представляет новую ферму Джона, а точка соединения \(N\) представляет город. Имеется \(M\) двунаправленных труб (\(1 \leq M \leq 1000\)), каждая их которых соединяет две точки соединения. \(i\)-ая труба стоит \(c_i\) долларов и может поддерживать передачу молока со скоростью \(f_i\) литров в секунду.

ФД хочет купить один путь (самый выгодный) из труб, конечными точками которого будут точки \(1\) и \(N\). Стоимость пути равна сумме стоимостей труб вдоль этого пути. Скорость передачи молока по пути равна минимальной из скоростей передачи труб (минимальное звено будет узким местом пути). ФД хочет максимизировать скорость передачи, делённую на стоимость пути. Гарантируется существование пути из \(1\) в \(N\).

Ферма состоит из \(N\) пастбищ (\(2 \leq N \leq 50,000\)), последовательно пронумерованных \(1 \dots N\). Коровы хотят добраться до амбара в пастбище \(N\). Каждое из остальных \(N-1\) пастбищ содержит ровно 1 корову. Коровы могут двигаться от пастбища к пастбищу по множеству из \(M\) ненаправленных дорожек (\(1 \leq M \leq 100,000\)). \(i\)-ая дорожка соединяет пару пастбищ \(a_i\) и \(b_i\), и требуется \(t_i\) единиц времени для её прохождения. Каждая корова может достичь амбара, пройдя некоторую последовательность дорожек.

Будучи голодными, коровы заинтересованы в остановках для еды на их пути домой. К счастью, \(K\) пастбищ содержат стоги сена (\(1 \leq K \leq N\)), \(i\)-ый из этих стогов сена имеет величину вкусности \(y_i\). Каждая хочет съесть один такой стог сена по дороге в амбар, но только если время, которое добавиться к её пути, не больше чем вкусность стога, который она съест. Заметим, что корова может съесть не более одного стога сена. Если на её пути встретятся другие пастбища со стогами, она просто игнорирует их.

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

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

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

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