Телекоммуникационная сеть крупной IT-компании содержит n серверов, пронумерованных от 1 до \(n\). Некоторые пары серверов соединены двусторонними каналами связи, всего в сети m каналов. Гарантируется, что сеть серверов устроена таким образом, что по каналам связи можно передавать данные с любого сервера на любой другой сервер, возможно с использованием одного или нескольких промежуточных серверов.

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

На рис. 1 показан пример сети и отказоустойчивого множества из серверов с номерами 1 и 4. Данные на сервер 2 можно передать следующим образом. При недоступности канала между серверами 1 и 2 — с сервера 4, при недоступности канала между серверами 2 и 3 — с сервера 1. На серверы 3 и 5 при недоступности любого канала связи можно по другим каналам передать данные с сервера 4.

Требуется написать программу, которая по заданному описанию сети определяет следующие числа: \(k\) — минимальное количество серверов в отказоустойчивом множестве серверов, \(c\) — остаток от деления количества способов выбора отказоустойчивого множества из \(k\) серверов на число \(10^9 + 7\)

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

Участок поверхности планеты, на котором планируется добывать полезные ископаемые, представляет собой клетчатый прямоугольник размером \(w\) на \(h\), клетки участка имеют координаты от (1, 1) до \((w, h)\). В некоторых клетках участка находятся базы специалистов, в которые могут быть доставлены партии роботов. Всего на участке размещено \(s\) баз, и \(i\)-я база находится в клетке с координатами \((x_i , y_i)\).

Каждая партия роботов характеризуется тремя параметрами: \(j\)-я партия доставляется на базу \(b_j\) , содержит \(n_j\) роботов и каждый робот партии обладает мобильностью \(m_j\) .

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

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

Руководством проекта получена информация о \(t\) партиях роботов, которые могут быть последовательно отправлены на планету. После доставки всех партий роботов, учитывая их ограниченную мобильность, возможна ситуация, что не удастся разместить роботов на участке так, чтобы в каждой клетке оказалось не больше \(q\) роботов. Поэтому руководство должно выбрать \(k\) первых партий роботов, где \(0 \le k \le t\), которые будут полностью доставлены на соответствующие базы. После этого, если \(k < t\), следует дополнительно принять \(z\) из \(n_{k + 1}\) роботов следующей, (\(k + 1\))-й партии, \(0 \le z < n_{k + 1}\).

Все полученные таким образом роботы должны с учетом ограничения на мобильность разместиться на участке таким образом, чтобы в каждой клетке было не более \(q\) роботов. После этого они будут активированы и начнут добычу полезных ископаемых. Разумеется, руководство проекта старается максимизировать количество роботов, которые будут доставлены на планету, поэтому, с учетом описанных ограничений, требуется максимизировать \(k\), а затем максимизировать \(z\).

Требуется написать программу, которая по размерам участка, числу \(q\), описанию расположения баз, а также количеству запланированных партий роботов и их описанию определяет максимальное число \(k\) — количество партий роботов, и затем – максимальное число \(z\) – дополнительное количество роботов из (\(k + 1\))-й партии, чтобы, доставив роботов на планету, их можно было разместить на участке таким образом, чтобы в каждой клетке оказалось не более \(q\) роботов.

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

Посылки принимаются в клиентских почтовых пунктах. Почтовый пункт принимает посылки, вес каждой из которых составляет целое число килограммов. Минимальный вес посылки равен 1 кг, а максимальный вес — \(k\) кг. Принятые посылки помещаются в специальный пакет.

Если после приема очередной посылки суммарный вес посылок в пакете больше или равен \(x\) кг, то пакет доставляется в муниципальный почтовый центр, где пакет с посылками перемещается в специальный контейнер.

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

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

Требуется написать программу, которая по заданным значениям \(k\) — максимального веса посылки, \(x\) — необходимого веса пакета для его отправки в муниципальный почтовый центр, и \(y\) — необходимого веса контейнера для его отправки в региональный сортировочный центр, определяет минимальный вес контейнера при его перевозке.

Группа ученых работает в международной научной лаборатории, которая занимается исследованиями поведения элементарных частиц в установке для экспериментов «Большой линейный коллайдер» (БЛК). Установка БЛК представляет собой прямую, в некоторых точках которой размещаются частицы, которые могут перемещаться вдоль прямой.

В очередном эксперименте в БЛК размещаются n частиц, каждая из которых представляет собой либо отрицательно заряженную частицу — электрон \(е^–\) , либо положительно заряженную частицу — позитрон \(е^{+}\) . В эксперименте \(i\)-я частица исходно размещается в точке с координатой \(x_i\) . После начала эксперимента в результате работы БЛК частицы начнут перемещаться в разные стороны вдоль прямой: \(е^{–}\) частицы перемещаются по направлению уменьшения координаты, а \(е^{+}\) частицы — по направлению увеличения координаты. Абсолютные величины скоростей всех частиц одинаковы и равны 1.

Если в процессе перемещения частицы \(е^{–}\) и \(е^{+}\) оказываются в одной точке, то они взаимодействуют и обе исчезают, при этом они не влияют на дальнейшее поведение остальных частиц.

Ученые выбрали \(m\) различных моментов времени \(t_1, t_2, \dots, t_m\), для каждого из которых их интересует, какое количество частиц находится в БЛК непосредственно после каждого из этих моментов времени. Отсчет времени начинается с момента 0, когда частицы приходят в движение. Частицы, исчезнувшие в результате взаимодействия в момент времени \(t_j\) , не должны учитываться при подсчете количества частиц для этого момента времени.

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

В физико-биологической лаборатории исследуют воздействие излучения на растения при облучении через силовые поля.

Экспериментальная установка содержит квадратную платформу размером \(10^9 \times 10^9\) , заполненную плодородной почвой. Над платформой установлен источник излучения. Между источником излучения и платформой можно включать \(n\) силовых полей.

Генератор силовых полей установлен над точкой (0, 0). При этом \(i\)-е силовое поле представляет собой прямоугольник со сторонами, параллельными границам платформы и координатами двух противоположных углов (0, 0) и \((x_i , y_i)\).

В эксперименте планируется изучать воздействие излучения на растения при облучении через \(k\) силовых полей. Из заданных n полей необходимо выбрать \(k\) полей для эксперимента. Ученые хотят выбрать силовые поля таким образом, чтобы площадь участка платформы, над которой находятся все \(k\) выбранных силовых полей, была максимальна.

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