Страница: 1 2 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

Стена осаждённой крепости состоит из 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 — количество участков стены и $s$ — количество защитников крепости ($1 \le n \le 100 000; 1 \le s \le 10^9$ ).

Следующие n строк содержат по два целых числа $a_i , k_i$ — общее количество нападающих на $i$-й участок стены и количество нападающих, атаку которых может отразить один защитник этого участка ($1 \le a_i , k_i \le 10^9$ ).

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

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

Таблица системы оценивания

Пояснения к примерам

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

Примеры
Входные данные
1 10
8 1
Выходные данные
0
Входные данные
3 3
4 2
1 1
10 8
Выходные данные
3
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

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

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

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

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

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

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

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

В первой строке входных данных записаны целые числа $n$, $m$ и $g$, где $n$ и $m$ — размеры поля с севера на юг и с запада на восток соответственно
($1 \le n, m \le 1000$), а $g$ — признак, равный 1 или 0, обозначающий необходимость определения клеток и моментов времени для активации роботов.

Последующие $n$ строк по $m$ символов в каждой описывают цвета клеток поля и разрешение на активацию робота в них. Цвет поля задаётся английской буквой, соответствующей направлению движения: «N» или «n» — север, «S» или «s» — юг, «E» или «e» — восток и «W» или «w» — запад.

Клетки, в которых исходно размещены неактивированные роботы, обозначены заглавными буквами, а клетки, в которых исходно робота нет — строчными. Гарантируется, что на поле находится хотя бы один неактивированный робот.

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

В первой строке выходных данных выведите одно число $k$ — максимально возможный результат эксперимента. Для входных данных, в которых значение $g$ равно 1, в каждой из последующих $k$ строк выведите три целых числа $r$, $c$ и $t$: номера строки и столбца, описывающие клетку для активации робота, и момент времени для его активации соответственно ($1 \le r \le n; 1 \le c \le m; 1 \le t \le 10^9$ ). Строки нумеруются от 1 до $n$ сверху вниз (с севера на юг), а столбцы — от 1 до $m$ слева направо (с запада на восток).

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

Таблица системы оценивания

Пояснения к примерам

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

Во втором примере приведённый ответ не является единственным.

В третьем примере активированные в клетках (4, 1) и (4, 3) роботы могут перемещаться между клетками (4, 2) и (4, 3) сколько угодно раз, не сталкиваясь при этом.

Примеры
Входные данные
3 4 0
SSSS
EESW
ENWW
Выходные данные
4
Входные данные
3 4 1
SSSS
EeSW
ENwW
Выходные данные
4
1 1 26
1 2 26
1 3 22
1 4 20
Входные данные
4 4 1
essS
Eess
Snww
EeWN
Выходные данные
5
1 4 31
2 1 34
3 1 32
4 1 32
4 4 30
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

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

Они получили сезонное разрешение на лов рыбы в $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$, $m$ и $p$ — количество точек лова рыбы, количество оптовых баз и стоимость топлива
($1 \le n, m \le 500 000; 0 \le p \le 10^9 $).

Следующие $n$ строк содержат по два целых числа $x_i$ и $a_i$ — расстояние от устья и максимальный улов для каждой точки лова рыбы ($0 < x_1 < x_2 < \dots < x_n \le 10^9 ; 0 < a_i \le 10^6$ ).

Следующие $m$ строк содержат по три целых числа $y_j, b_j, c_j$ — расстояние от устья, максимальное закупаемое количество тонн рыбы и цена закупки за тонну для каждой оптовой базы ($0 < y_1 < y_2 < \dots < y_m \le 10^9 ; 0 < b_j, c_j \le 10^6$ ).

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

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

Таблица системы оценивания

Пояснение к примерам

Во втором примере оптимальными будут следующие действия. Следует доплыть до точки на расстоянии 6 километров от устья, потратив 600 рублей на топливо, и выловить в ней 5 тонн рыбы. После этого следует спуститься на 1 километр по реке к базе на расстоянии 5 километров от устья и продать выловленную рыбу по цене 2000 рублей за тонну. Затем следует вернуться в устье реки. Суммарная прибыль составит 9400 рублей.

Примеры
Входные данные
3 2 0
1 5
2 3
4 5
2 2 10
3 6 5
Выходные данные
50
Входные данные
2 1 100
6 5
100 4
5 100 2000
Выходные данные
9400
Входные данные
3 3 10
1 1
10 100
20 10
2 1000 1
11 50 50
17 50 2
Выходные данные
2441
ограничение по времени на тест
7.0 second;
ограничение по памяти на тест
512 megabytes

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

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

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

Участок горной цепи в этом районе представлен ломаной, состоящей из 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$.

Точка $A (x_A, y_A)$ находится в прямой видимости из точки $B (x_B, y_B)$, если ни одна точка отрезка AB не находится строго под ломаной.

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

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

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

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

Первая строка входных данных содержит два числа $n$ и $q$ ($1 \le n, q \le 400 000$) — количество звеньев ломаной и количество вариантов расположения башни.

Ограничения на величины последующих входных данных зависят от значения константы $C$, которая может быть равна $10^4$ или $10^9$ в зависимости от подзадачи (см. таблицу системы оценивания).

Каждая из последующих $n$ строк содержит по два целых числа $d_i , k_i (1 \le d_i \le C; −C \le k_i \le C$) — проекцию на ось $x$ и угловой коэффициент $i$-го звена ломаной ($0 = x_0 < x_1 < \cdots < x_i < \cdots < x_n \le C; y_0 = y_n = 0; −C \le y_i \le C$).

Каждая из последующих $q$ строк содержит по два целых числа $u_j, v_j (0 \le u_j \le C, −C \le v_j \le C$) — координаты верхней точки башни в $j$-м варианте расположения.

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

Выходные данные должны содержать $q$ строк, в каждой из которых находятся по два целых числа $l_j$ и $r_j$ — $x$-координаты двух точек, до которых добегут разведчики, направляющиеся на запад и на восток соответственно в $j$-м варианте расположения башни. Гарантируется, что числа $l_j$ и $r_j$ являются целыми.

Таблица системы оценивания

Замечание

Обратите внимание, что все точки отрезка между (6, 2) и (7, 1) находятся в прямой видимости из верхней точки башни согласно определению в условии.
В данном тесте нижние точки всех вариантов башен совпадают.
В данном тесте верхние точки башен всех вариантов находятся на одной горизонтальной прямой. Обратите внимание, что нижняя точка башни может совпадать с одним из концов горной цепи.
В четвёртом тесте показывается, что в стране Неизвестных Отцов горная цепь может целиком находиться ниже уровня её концов.

Примеры
Входные данные
6 1
3 1
2 -1
1 1
1 -1
1 1
2 -1
5 3
Выходные данные
3 8
Входные данные
5 3
1 1
1 -2
2 0
2 1
1 -1
3 0
3 5
3 3
Выходные данные
1 6
0 7
0 6
Входные данные
6 4
1 2
2 -2
1 1
1 -2
4 1
1 -1
1 4
3 4
10 4
7 4
Выходные данные
0 4
1 9
4 10
1 10
Входные данные
8 4
1 -3
2 0
1 1
2 0
1 -3
1 3
1 2
1 0
2 -2
6 -1
6 4
7 -4
Выходные данные
0 6
4 9
0 10
6 9
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
512 megabytes

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

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

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

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

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

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

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

Первая строка входных данных содержит два целых числа: $n$ — количество рядов и $m$ — количество мониторов в каждом ряду ($2 \le n, m \le 1000$). Следующие $n$ строк описывают ряды мониторов в порядке сверху вниз. Каждая из этих строк содержит по $m$ символов, описывающих мониторы в соответствующем ряду в порядке слева направо. Символ «1» означает, что на монитор выводится изображение из первого здания, а символ «2» — из второго здания.

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

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

Таблица системы оценивания

Пояснения к примерам

В первом примере с помощью команды «вправо», можно получить слева удобный для наблюдения блок из единиц, а справа — удобный для наблюдения блок из двоек.

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

В третьем примере, например, командами «вправо» и «вниз» можно добиться наличия трёх удобных для наблюдения блоков из единиц.

Примеры
Входные данные
2 4
1221
1221
Выходные данные
2
Входные данные
3 2
22
22
22
Выходные данные
2
Входные данные
3 3
111
121
111
Выходные данные
3

Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест