На олимпиаду по программированию в город Н. приехало много школьников из других регионов. Все они размещены в $$$n$$$ комнатах на одном этаже гостиницы. Эти комнаты были пронумерованы числами от $$$1$$$ до $$$n$$$ в порядке следования по этажу.
Изначально в комнате с номером $$$i$$$ живет $$$a_i$$$ школьников. Все школьники уже подружились между собой, пока ожидали заселения. Однако теперь они хотят стать близкими друзьями! Два друга считаются близкими, если они находятся довольно близко друг к другу — номера их комнат должны отличаться не более чем на $$$k$$$. Посчитайте, какому наименьшему количеству школьников придется переехать в другую комнату, чтобы все присутствующие на олимпиаде стали близкими друзьями. Можно считать, что любая комната способна вместить сколь угодно большое количество детей.
Первая строка содержит два натуральных числа — $$$n$$$ и $$$k$$$ ($$$0 \leq k \lt n \leq 2\cdot 10^5$$$).
Вторая строка содержит $$$n$$$ чисел $$$a_i$$$ ($$$0 \leq a_i \leq 1000$$$).
Выведите одно число — наименьшее количество детей, которые должны сменить комнату.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные | Необходимые | Информация |
| ограничения | подзадачи | о проверке | ||
| $$$1$$$ | $$$5$$$ | $$$k = 0$$$ | первая ошибка | |
| $$$2$$$ | $$$10$$$ | $$$k = 1$$$ | 1 | первая ошибка |
| $$$3$$$ | $$$30$$$ | $$$n \leq 1000$$$ | первая ошибка | |
| $$$4$$$ | $$$10$$$ | $$$k \leq 10$$$ | 1,2 | первая ошибка |
| $$$5$$$ | $$$15$$$ | $$$a_i \leq 1$$$ | первая ошибка | |
| $$$6$$$ | $$$30$$$ | нет | 1,2,3,4,5 | первая ошибка |
7 00 0 1 1 0 0 1
2
7 10 0 1 1 0 0 1
1
7 10 0 1 1 0 0 3
2
В первом примере всем нужно жить в одной комнате, поэтому два человека должны переехать.
Во втором примере можно жить в двух соседних комнатах, поэтому школьник из комнаты $$$7$$$ может переехать, например, в комнату $$$3$$$.
В третьем примере всем школьникам стоит собраться в последней комнате.
У Дианы есть число $$$n$$$. Она может выполнять операции двух видов с этим числом:
- поменять местами любые две цифры числа, например, из числа $$$31$$$ можно получить число $$$13$$$, а из числа $$$201$$$ — число $$$102$$$;
- увеличить число на $$$1$$$.
В операции первого типа запрещается ставить цифру $$$0$$$ на первое место в числе (иными словами, ведущие нули запрещены). Например, из числа $$$30$$$ нельзя получить число $$$3$$$.
Диане стало интересно, какое наименьшее число она может получить из $$$n$$$ при помощи этих операций? Операции разрешается делать произвольное число раз в любом порядке.
Первая строка содержит натуральное число $$$n$$$ ($$$1 \leq n \leq 10^9$$$).
Вывести одно число — минимальное число, которое можно получить из $$$n$$$.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные | Необходимые | Информация |
| ограничения | подзадачи | о проверке | ||
| $$$1$$$ | $$$1$$$ | $$$n \leq 9$$$ | первая ошибка | |
| $$$2$$$ | $$$20$$$ | $$$10 \leq n \leq 99$$$ | первая ошибка | |
| $$$3$$$ | $$$22$$$ | $$$100 \leq n \leq 999$$$ | первая ошибка | |
| $$$4$$$ | $$$22$$$ | $$$100 \leq n \leq 2\cdot 10^5$$$ | 3 | первая ошибка |
| $$$5$$$ | $$$35$$$ | нет | 2,3,4 | первая ошибка |
5
5
28
12
Во втором примере Диана может сначала увеличить число до $$$31$$$, затем поменять цифры местами и получить число $$$13$$$, потом увеличить его до $$$21$$$, и, наконец, преобразовать его в число $$$12$$$. Можно доказать, что меньшие числа получить невозможно.
Вася играет в популярную стратегию «Heroes of Light and Magic II».
Самая важная битва против армии противника началась! Герой Васи вступил в бой и должен одержать великую победу! Однако, когда армия вражеского героя была полностью отрисована, Вася заметил, что она содержит лишь один отряд из $$$n$$$ одинаковых странных юнитов, которых Вася не встречал раньше (юнит — игровая единица (персонаж) в компьютерных стратегических играх). К сожалению, у Васи не работает правая кнопка мыши, поэтому он не может посмотреть характеристики вражеского юнита и узнать количество единиц здоровья $$$x$$$ этого существа. Однако в армии Васи есть могучий феникс, который является самым быстрым существом в игре!
Всего Вася $$$m$$$ раз атаковал фениксом вражеский отряд, и каждая из этих атак нанесла ровно $$$d$$$ единиц урона. После каждой атаки Вася записывал количество оставшихся юнитов во вражеском отряде. Зная эти числа, уже можно оценить, сколько же здоровья у неизвестного юнита. Помогите Васе — найдите наименьшее и наибольшее возможное количество единиц здоровья $$$x$$$, которым может обладать неизвестный вражеский юнит.
Напоминаем, как считается количество юнитов в отряде при получении урона. Если юнит обладает $$$x$$$ единицами здоровья, то отряд из $$$n$$$ таких юнитов в сумме содержит $$$n \cdot x$$$ единиц здоровья. При получении урона $$$d$$$ сначала урон наносится первому юниту. Если текущее количество единиц здоровья $$$h$$$ первого юнита строго больше $$$d$$$, то здоровье первого юнита уменьшается на $$$d$$$, и атака заканчивается. В противном случае первый юнит погибает (в отряде становится на одного юнита меньше), а оставшийся урон уменьшается на $$$h$$$. Этот урон наносится следующему юниту (у которого изначально $$$x$$$ единиц здоровья) и так далее, пока очередной юнит не сможет выдержать урон (то есть остаться с положительным числом единиц здоровья после атаки).
В первой строке заданы три натуральных числа — $$$n$$$, $$$m$$$ и $$$d$$$ ($$$2 \leq n \leq 10^9$$$, $$$1 \leq m \leq 2 \cdot 10^{5}$$$, $$$1 \leq d \leq 10^9$$$).
Во второй строке заданы $$$m$$$ натуральных чисел $$$c_i$$$ — количество юнитов во вражеском отряде после очередной атаки феникса ($$$1 \leq c_i \leq n$$$). Гарантируется, что числа $$$c_i$$$ идут в порядке невозрастания и в результате всех атак хотя бы один юнит был уничтожен и хотя бы один юнит остался жив, то есть $$$1 \leq c_m \lt n$$$. Гарантируется, что данные непротиворечивы, то есть существует хотя бы одно натуральное число $$$x$$$, удовлетворяющее входным данным.
Вывести два числа — минимальное и максимальное возможное количество единиц здоровья у неизвестного юнита.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные | Необходимые | Информация |
| ограничения | подзадачи | о проверке | ||
| $$$1$$$ | $$$8$$$ | $$$m = 1$$$ | первая ошибка | |
| $$$2$$$ | $$$12$$$ | $$$n = 2$$$ | первая ошибка | |
| $$$3$$$ | $$$5$$$ | $$$d = 1$$$ | первая ошибка | |
| $$$4$$$ | $$$25$$$ | $$$n, m, d \leq 100$$$ | первая ошибка | |
| $$$5$$$ | $$$25$$$ | $$$d \leq 100$$$ | 3 | первая ошибка |
| $$$6$$$ | $$$25$$$ | нет | 1,2,3,4,5 | первая ошибка |
17 1 20 15
7 10
В примере после атаки феникса (с уроном $$$20$$$ единиц) погибло $$$2$$$ юнита. Это могло случиться, если у каждого из них было $$$7$$$, $$$8$$$, $$$9$$$ или $$$10$$$ единиц здоровья.
Иллюстрация атакующего феникса:
Как-то раз перед первым уроком Вася и Петя взяли один листок бумаги, который представлял собой прямоугольник $$$n\times m$$$ клеток ($$$n$$$ строк, $$$m$$$ столбцов). Ребята начали отмечать на нём клетки: Вася отмечал клетки красным цветом, а Петя — синим. Вася с Петей так увлеклись клетками, что не заметили, как до начала первого урока осталось лишь 5 минут. К сожалению, ребята сидят за разными партами и не смогут вместе отмечать клетки после начала урока.
Сейчас они уже успели отметить $$$k$$$ клеток. Далее ребята решили разрезать листок на две части так, чтобы выполнялись следующие условия:
- разрез является вертикальной или горизонтальной прямой, которая проходит по линиям сетки прямоугольника;
- все отмеченные красные клетки находятся с одной стороны от разреза (эта часть листка достанется Васе);
- все отмеченные синие клетки находятся с другой стороны от разреза (эта часть листка достанется Пете).
К сожалению, не всегда можно сделать разрез, удовлетворяющий условиям выше. Поэтому ребята решили перекрасить несколько клеток (из синей клетки при перекрашивании получается красная и наоборот), чтобы можно было сделать требуемый разрез. В частности, если после перекрашивания все отмеченные клетки будут одного цвета, то весь листок можно отдать одному из мальчиков, то есть одна из частей после разреза будет пустой.
Помните, что времени до урока осталось мало, поэтому нужно найти, какое наименьшее количество клеток надо перекрасить, чтобы можно было осуществить разрез.
Первая строка содержит три натуральных числа — $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \leq n, m \leq 10^9$$$, $$$1 \leq k \leq 2\cdot 10^5$$$).
Каждая из следующих $$$k$$$ строк содержит три числа, описывающих очередную отмеченную клетку — $$$x_i$$$, $$$y_i$$$, $$$c_i$$$ ($$$1 \leq x_i \leq n$$$, $$$1 \leq y_i \leq m$$$, $$$0 \leq c_i \leq 1$$$). Где $$$x_i$$$ и $$$y_i$$$ — номер строки и столбца очередной отмеченной клетки, а $$$c_i$$$ — цвет клетки: $$$0$$$ соответствует красной клетке, $$$1$$$ — синей.
Выведите одно число — наименьшее количество клеток, которое необходимо перекрасить.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные | Необходимые | Информация |
| ограничения | подзадачи | о проверке | ||
| $$$1$$$ | $$$14$$$ | $$$n, m, k \leq 8$$$ | первая ошибка | |
| $$$2$$$ | $$$10$$$ | $$$n = 1$$$ и $$$m \leq 2\cdot 10^5$$$ | первая ошибка | |
| $$$3$$$ | $$$18$$$ | $$$n, m \leq 1000$$$, все $$$x_i$$$ и все $$$y_i$$$ различны | первая ошибка | |
| $$$4$$$ | $$$11$$$ | $$$n, m \leq 100$$$ | 3 | первая ошибка |
| $$$5$$$ | $$$27$$$ | все $$$x_i$$$ и все $$$y_i$$$ различны | 3 | первая ошибка |
| $$$6$$$ | $$$20$$$ | нет | 1,2,3,4,5 | первая ошибка |
1 3 3 1 2 1 1 1 0 1 3 0
1
2 3 3 2 2 1 1 1 0 1 3 0
0
2 2 4 1 1 0 1 2 1 2 1 1 2 2 0
2
Иллюстрация ко второму примеру:
Штриховкой обозначены клетки красного цвета, сплошной заливкой – единственная клетка синего цвета.
