Известный Ментат основал университет изучения вселенной Дюны и теперь распределяет ресурс пряности между своими подопечными. Всего ему предстоит распределить $$$n$$$ единиц пряности, каждая из которых предназначена для исследований в области направления номер $$$a_i$$$.
По правилам, установленным императором, одному обучаемому нельзя выделить две единицы пряности для изучений по совпадающим или похожим направлениям. Направления с номерами $$$a_i$$$ и $$$a_j$$$ считаются похожими, если разница между их номерами не превышает $$$k$$$, то есть если $$$|a_i - a_j| \le k$$$.
Пряность — ценнейшее и редчайшее вещество во вселенной, которое способно ускорить человеческий мозг до уровня суперкомпьютера, поэтому Ментат упорядочил студентов по их способностям и хочет распределить пряность между как можно меньшим количеством наиболее способных студентов. Например, пряность для изучения направлений $$$1$$$, $$$2$$$ и $$$4$$$ при $$$k = 2$$$ можно выдать двум студентам (первому — $$$1$$$ и $$$4$$$, второму — $$$2$$$), но нельзя выдать все одному студенту, потому что направления $$$1$$$ и $$$2$$$ похожи.
Необходимо определить, какое минимальное количество обучаемых достаточно, чтобы весь предоставленный ресурс пряности мог быть распределен, соблюдая правила императора.
В первой строке ввода через пробел даны два целых числа $$$n$$$ и $$$k$$$ — количество единиц пряности и число, задающее, какие направления изучения вселенной считаются похожими ($$$1 \le n \le 2 \cdot 10^5$$$; $$$0 \le k \le 10^9$$$).
Во второй строке через пробел перечислены $$$n$$$ чисел $$$a_i$$$ — направления, для изучения которых нужна пряность ($$$1 \le a_i \le 10^9$$$).
Выведите единственное целое число — минимальное количество студентов, по которым можно распределить весь объем пряности.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Доп. ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | – | примеры из условия | полная | |
| 1 | 7 | $$$n \le 3$$$ | полная | |
| 2 | 13 | $$$k = 0$$$ | полная | |
| 3 | 15 | $$$n \le 9$$$ | 0, 1 | первая ошибка |
| 4 | 18 | $$$n \le 1000$$$, $$$1 \le k \le 2$$$, все $$$a_i$$$ различны | первая ошибка | |
| 5 | 22 | $$$n \le 1000$$$ | 0, 1, 3, 4 | первая ошибка |
| 6 | 25 | нет | 1 – 5 | первая ошибка |
3 2 1 2 4
2
9 2 7 1 2 8 5 4 9 3 6
3
3 0 3 1 1
2
4 4 1 100 77 32
1
Пояснения к первому примеру даны в условии.
Во втором примере к условию достаточно выдать каждому из трех студентов единицы пряности с одинаковым остатком по модулю $$$3$$$. Двух студентов недостаточно, потому что никакие две из единиц пряности по направлениям $$$1$$$, $$$2$$$ и $$$3$$$ не могут достаться одному студенту.
В третьем примере к условию две единицы пряности по одному и тому же направлению $$$1$$$ должны быть отданы разным студентам, тогда как единицу пряности по направлению $$$3$$$ можно будет после отдать любому из них.
В четвертом примере к условию все единицы пряности могут быть выданы одному студенту, и правила императора не будут нарушены.
Пряность или меланж — один из самых ценных ресурсов во вселенной. Когда Дом Атрейдесов прибыл на планету Арракис, им было поручено в том числе наладить добычу пряности после того, как планету покинул Дом Харконненнов.
На первых этапах Атрейдесам был доступен только один харвестер (комбайн) для сбора, поэтому необходимо было срочно наладить их производство.
- Компонент I для харвестера можно произвести за $$$t_1$$$ времени из металлолома, которого в пустыни Арракиса неограниченное количество.
- Компонент II производится из уже готового первого компонента за $$$t_2$$$ времени.
- Харвестер производится за $$$t_3$$$ времени из одного компонента I и одного компонента II.
Первый этап производства довольно быстрый: гарантируется, что $$$1 \le t_1 \le 2$$$. За каждый этап производства отвечает отдельная фабрика, и каждая фабрика может работать только над соответствующим этапом (то есть, например, на фабрике, производящей компонент II, нельзя производить компонент I).
Все три процесса могут происходить параллельно, то есть пока, например, какой-то компонент I находится в производстве, другой уже произведенный ранее может обрабатываться в компонент II. Однако каждая из трех необходимых фабрик доступна в единственном числе, и в каждый момент времени может работать не более чем над одним компонентом или харвестером.
Чтобы быстро наладить добычу пряности, необходимо произвести $$$n$$$ харвестеров. За какое минимальное время это можно сделать?
В первой строке ввода дано единственное целое число $$$n$$$ — количество харвестеров, которые требуется произвести ($$$1 \le n \le 1000$$$).
Во второй строке через пробел даны три целых числа $$$t_1$$$, $$$t_2$$$ и $$$t_3$$$ — время, необходимое на каждом из этапов производства для получения единицы соответствующего продукта ($$$1 \le t_1 \le 2$$$; $$$1 \le t_2, t_3 \le 10^5$$$).
Выведите единственное целое число — минимальное время, необходимое для производства $$$n$$$ харвестеров.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Доп. ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | – | примеры из условия | полная | |
| 1 | 7 | $$$n = 1$$$ | полная | |
| 2 | 11 | $$$t_1 = t_2 = 1$$$, $$$t_3 \ge 2$$$ | полная | |
| 3 | 15 | $$$t_1 = 1$$$ | 2 | первая ошибка |
| 4 | 10 | $$$t_1 = t_2 \ge t_3$$$ | первая ошибка | |
| 5 | 10 | $$$t_1 = t_2$$$ | 2, 4 | первая ошибка |
| 6 | 15 | $$$n \le 6$$$, $$$t_2, t_3 \le 3$$$ | первая ошибка | |
| 7 | 19 | $$$n \le 100$$$, $$$t_2, t_3 \le 100$$$ | 0, 6 | первая ошибка |
| 8 | 13 | нет | 0 – 7 | первая ошибка |
1 1 5 6
12
2 2 1 4
12
10 1 7 20
208
В первом примере к условию:
- Можно произвести первый компонент типа I в момент времени $$$1$$$, после чего вторая фабрика может сразу начать из нее изготавливать компонент II.
- В момент времени $$$1 + 5 = 6$$$ он будет готов, и к этому времени первая фабрика произведет еще $$$5$$$ компонентов типа I.
- Один из них вместе с только что изготовленным компонентом типа II можно сразу же передать на третью фабрику, и в момент времени $$$6 + 6 = 12$$$ изготовить харвестер.
Барон Владимир Харконнен похитил жену Веллингтона Юэ (личного доктора герцога Лето Атрейдеса). Чтобы вернуть ее, Юэ должен предать герцога Лето и снять оборону города. Чтобы снять силовой щит, покрывающий город, требуется ввести специальный код.
Юэ знает про код, что:
- он состоит из цифр от $$$1$$$ до $$$9$$$;
- его длина в точности равна $$$2n$$$;
- сумма первых $$$n$$$ цифр отличается от суммы последних $$$n$$$ цифр не более чем на один;
- произведение первых $$$n$$$ цифр равно произведению последних $$$n$$$ цифр.
Помогите Юэ узнать, сколько существует кодов длиной $$$2n$$$, чтобы он мог спасти свою жену.
Дано одно целое число $$$n$$$, где $$$2n$$$ — длина кода, снимающего щит ($$$1 \le n \le 42$$$).
Вывести количество кодов длины $$$2n$$$.
В этой задаче 42 теста. Все тесты оцениваются независимо.
| Тесты | Баллы | Доп. ограничения |
| 1, 2 | – | примеры из условия |
| 3 – 12 | $$$10 \times 4$$$ | $$$n \le 12$$$ |
| 13 – 42 | $$$30 \times 2$$$ | нет |
1
9
2
177
Во втором примере из условия подходят
- $$$9$$$ кодов из четырех одинаковых цифр
- $$$9 \cdot 8 \cdot 2 = 144$$$ кода, в которых первые две цифры различны и совпадают в каком-то порядке с последними двумя;
- $$$4$$$ кода, состоящих из цифр $$$1$$$ и $$$4$$$ в одной половине и двух цифр $$$2$$$ в другой;
- $$$8$$$ кодов, состоящих из цифр $$$2$$$ и $$$6$$$ в одной половине и цифр $$$3$$$ и $$$4$$$ в другой;
- $$$8$$$ кодов, состоящих из цифр $$$3$$$ и $$$8$$$ в одной половине и цифр $$$4$$$ и $$$6$$$ в другой;
- $$$4$$$ кода, состоящих из цифр $$$4$$$ и $$$9$$$ в одной половине и двух цифр $$$6$$$ в другой.
Новый архитектор Арракиса проектирует новый городоской квартал Арракина, состоящий из $$$n$$$ расположенных в ряд зданий. Здание номер $$$i$$$ имеет ровно $$$h_i$$$ этажей.
Теперь архитектору интересно, смогут ли горожане по достоинству оценить его проект. Проблема в том, что в городе часто случаются песчаные бури, а стены города защищают от них только нижние этажи, поэтому верхние этажи некоторых зданий может быть не видно с земли.
Формально, вам поступают запросы вида $$$(l, r, f)$$$ — «уровень песчаной бури вокруг зданий с $$$l$$$-го по $$$r$$$-й включительно становится равен $$$f$$$». Это означает, что у всех зданий с $$$l$$$-го по $$$r$$$-й становится видно только первые $$$f$$$ этажей, тогда как все этажи выше спрятаны за песком и не видны. После каждого такого запроса вы должны сообщить архитектору, сколько всего этажей всех его зданий видно с земли.
Еще раз отметим, что песчаная буря непрерывна вверх, то есть если этаж номер $$$x$$$ здания номер $$$y$$$ спрятан за песком, то этажи $$$x + 1, x + 2, \ldots, h_y$$$ также спрятаны, и видны только этажи с первого по $$$(x - 1)$$$-й.
Изначально, перед поступлением первого запроса, песчаная буря еще не началась, то есть все здания видны целиком.
В первой строке ввода через пробел даны два целых числа $$$n$$$ и $$$q$$$ — количество зданий и количество запросов на изменение уровня песчаной бури ($$$1 \le n, q \le 10^5$$$).
Во второй строке ввода через пробел перечислены $$$n$$$ целых чисел $$$h_i$$$ — высоты зданий ($$$1 \le h_i \le 10^9$$$).
В следующих $$$q$$$ строках даны описания запросов. В $$$i$$$-й из них через пробел даны числа $$$l_i$$$, $$$r_i$$$ и $$$f_i$$$ — границы отрезка, на котором меняется уровень песчаной бури, и сам новый уровень ($$$1 \le l_i \le r_i \le n$$$; $$$0 \le f_i \le 10^9$$$).
Выведите $$$q$$$ строк, каждая из которых содержит единственное целое число — ответ на соответствующий запрос.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Доп. ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | – | примеры из условия | полная | |
| 1 | 10 | все $$$h_i$$$ равны, запросы не пересекаются | полная | |
| 2 | 13 | $$$h_{i + 1} \ge h_i$$$, запросы не пересекаются | 1 | первая ошибка |
| 3 | 15 | $$$n, q \le 200$$$ | 0 | первая ошибка |
| 4 | 17 | $$$r_i - l_i \le 10$$$ для всех $$$i$$$ | 0 | первая ошибка |
| 5 | 20 | $$$n, q \le 2000$$$ | 0, 3 | первая ошибка |
| 6 | 25 | нет | 0 – 5 | первая ошибка |
1 3 100 1 1 50 1 1 120 1 1 0
50 100 0
4 5 1 5 7 3 1 3 1 2 4 2 2 3 5 1 4 3 3 4 100
6 7 13 10 14