Стена осаждённой крепости состоит из n участков, пронумерованных от 1 до \(n\). Разведка доложила, что противник планирует отправить на штурм участка стены с номером \(i\) отряд из \(a_i\) нападающих. Для обороны крепости на участки стены будут направлены в общей сложности \(s\) защитников.

Участки стены различаются качеством укрепления, что приводит к различной эффективности обороны: на участке стены с номером \(i\) каждый защитник способен отразить атаку \(k_i\) нападающих.

Пусть на участок с номером \(i\) отправлено \(x_i\) защитников. Тогда если количество нападающих не превышает величину \(x_i\) · \(k_i\) , то на этом участке ни один из нападающих не прорвётся в крепость. Иначе в крепость прорвутся (\(a_i − x_i · k_i\)) нападающих.

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

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

Эксперимент проходит на прямоугольном поле размером n×m клеток. В начале эксперимента в заданных клетках размещается по одному неактивированному роботу. По команде «Старт» запускается таймер, который подаёт сигнал в начале каждой секунды. После каждого сигнала таймера, но не позднее чем через \(T_{max} = 10^9\) секунд после команды «Старт», разрешается активировать некоторых роботов.

Каждая клетка поля закрашена в один из четырёх цветов, распознаваемых сенсором робота. Цвет обозначает направление движения из данной клетки в соседнюю: на север, юг, восток или запад. В момент сигнала таймера каждый активированный робот перемещается в соседнюю клетку в направлении, соответствующем цвету клетки, в которой он находится. Все активированные роботы перемещаются одновременно. Цвета клеток поля выбраны так, что при перемещении никакой робот не может выйти за пределы поля.

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

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

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

Владельцы рыболовецкого судна, ведущего промысел на реке Кама, решили в летнем сезоне оптимизировать свой бизнес.

Они получили сезонное разрешение на лов рыбы в \(n\) точках русла реки на расстояниях \(x_1, x_2, \dots , x_n\) километров от устья. При этом в точке с номером \(i\) разрешается выловить не более \(a_i\) тонн рыбы.

Выловленную рыбу можно продавать на m оптовых базах, расположенных вдоль берега реки в точках на расстояниях \(y_1, y_2, \dots , y_m\) километров от устья. При этом база в точке номер \(j\) готова в этом сезоне закупить не более \(b_j\) тонн рыбы по цене \(c_j\) рублей за тонну.

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

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

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

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

По мотивам фантастической повести

А. и Б. Стругацких «Обитаемый остров»

Правительство страны Неизвестных Отцов планирует построить в гористом районе на границе с Хонтией башню противобаллистической защиты.

Участок горной цепи в этом районе представлен ломаной, состоящей из n звеньев, последовательно соединяющих \(n\) + 1 вершину. Вершины пронумерованы числами от \(0\) до \(n\) в порядке возрастания координаты \(x\). Звенья пронумерованы числами от 1 до \(n\), при этом \(i\)-е звено соединяет вершины с номерами \(i\) − 1 и \(i\).

Вершина с номером 0 находится в точке (0, 0). Звено с номером \(i\) задано двумя числами \(d_i\) — длиной проекции на ось \(x\) и \(k_i\) — угловым коэффициентом. Таким образом, если вершина с номером \(i\) − 1 имеет координаты \((x_{i−1}, y_{i−1})\), то координаты \(i\)-й вершины можно вычислить как \((x_{i − 1} + d_i , y_{i−1} + k_i · d_i)\). Последняя вершина лежит на оси \(x\), то есть \(y_n = 0\).

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

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

Правительство подготовило \(q\) вариантов расположения башни, каждый из которых характеризуется двумя целыми числами (\(u_j , v_j\)) — координатами верхней точки башни. Требуется написать программу, которая для каждого варианта определяет \(x\)-координаты двух точек, до которых добегут разведчики.

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

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

Кнопка «влево» перемещает изображение с каждого монитора на монитор, находящийся слева от него. При этом изображение из самого левого монитора в каждом ряду перемещается на самый правый монитор этого ряда.

Аналогичным образом действуют кнопки «вправо», «вверх» и «вниз». Кнопка «вправо» перемещает изображение с каждого монитора на монитор, находящийся справа от него. Изображения из самого правого монитора в каждом ряду перемещаются на самый левый монитор этого ряда. Кнопка «вверх» перемещает изображение с каждого из мониторов на монитор, находящийся над ним. Изображения из самого верхнего ряда перемещаются на мониторы самого нижнего ряда. Кнопка «вниз» перемещает изображение с каждого из мониторов на монитор, находящийся под ним. Изображения из самого нижнего ряда перемещаются на мониторы самого верхнего ряда.

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

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