Том и Джерри нашли в шкафу прямоугольную шоколадку размера $$$n \times m$$$, состоящую из квадратных кусочков $$$1 \times 1$$$. Том разрешил Джерри сделать сколько угодно (возможно ноль) раз следующее действие:
- Сначала разрезать шоколадку на два прямоугольника с целыми сторонами по границе кусочков так, чтобы у этих двух прямоугольников была пара равных по длине сторон.
- Затем склеить прямоугольники обратно, совместив равные по длине стороны, и получив в итоге снова прямоугольную шоколадку. Если у прямоугольников есть несколько пар равных по длине сторон, Джерри может выбрать любую.
Том хочет, чтобы Джерри получил шоколадку с максимально возможным периметром. Если Джерри сможет решить такую задачу, Том отдаст шоколадку ему, а иначе сам съест и его, и шоколадку.
Помогите Джерри определить, какой максимальный периметр может иметь шоколадка после нескольких действий.
В первой строке через пробел даны два целых числа $$$n$$$ и $$$m$$$ — размеры шоколадки ($$$1 \le n, m \le 10^9$$$).
Выведите одно целое число — максимальный возможный периметр шоколадки.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 30 | $$$n \le 100$$$ | первая ошибка | |
| 2 | 30 | Одна из сторон шоколадки — степень двойки | первая ошибка | |
| 3 | 40 | Без дополнительных ограничений | 1, 2 | первая ошибка |
10 4
82
7 10
38
В первом примере Джерри может действовать следующим образом:
- Сначала разрезать шоколадку $$$10 \times 4$$$ на два прямоугольника $$$10 \times 2$$$ и $$$10 \times 2$$$.
- Склеить из прямоугольников шоколадку $$$20 \times 2$$$.
- Разрезать шоколадку $$$20 \times 2$$$ на два прямоугольника $$$20 \times 1$$$ и $$$20 \times 1$$$.
- Склеить из прямоугольников шоколадку $$$40 \times 1$$$.
Итоговый периметр будет равен $$$40 \cdot 2 + 1 \cdot 2 = 82$$$.
Том наконец-то смог поймать Джерри в ловушку. Ловушка представляет из себя резервуар с водой, в котором закреплены $$$n$$$ платформ. Платформа с номером $$$i$$$ находится на высоте $$$a_i$$$ относительно уровня воды в резервуаре.
Каждая платформа представляет определенный уровень опасности для Джерри. Если высота платформы $$$a_i \lt 0$$$, то платформа погружена под воду, и представляет опасность $$$-a_i$$$. Если же $$$a_i \geqslant 0$$$, то с платформы можно упасть, и ее опасность равна $$$a_i$$$. Таким образом, опасность $$$i$$$-й платформы равна в точности $$$|a_i|$$$.
У Тома есть доступ к панели управления платформами, которая позволяет ему изменить высоты всех платформ на одно и то же число $$$x$$$, то есть новая высота $$$i$$$-й платформы станет равна $$$a_i + x$$$. Пока Джерри не выбрался из ловушки, Том успеет $$$k$$$ раз воспользоваться панелью управления. Ваша задача — после каждого действия Тома посчитать суммарную опасность ловушки, то есть сумму опасностей всех платформ.
В первой строке ввода дано целое число $$$n$$$ — количество платформ в ловушке ($$$1 \leqslant n \leqslant 100\,000$$$). В следующей строке через пробел перечислены $$$n$$$ чисел $$$a_i$$$ — высоты ловушек ($$$|a_i| \leqslant 1\,000\,000$$$).
В третьей строке дано целое число $$$k$$$ — количество раз, которое Том будет менять высоты платформ ($$$1 \leqslant k \leqslant 100\,000$$$). В последней строке ввода даны $$$k$$$ чисел $$$x_i$$$, где $$$x_i$$$ — величина, на которую Том изменяет высоты платформ $$$i$$$-м действием ($$$|x_i| \leqslant 1\,000\,000$$$).
После каждого действия Тома, выведите на новой строке суммарную опасность ловушки.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 10 | $$$n \cdot k \leqslant 100\,000$$$ | первая ошибка | |
| 2 | 10 | $$$|a_i| \leqslant 10$$$ | первая ошибка | |
| 3 | 20 | В каждый момент времени модули высот не превосходят $$$10^4$$$ | первая ошибка | |
| 4 | 20 | $$$x_i \geqslant 0$$$ | первая ошибка | |
| 5 | 40 | Без дополнительных ограничений | 1, 2, 3, 4 | первая ошибка |
3 2 3 1 3 -1 -2 4
3 3 9
5 1 2 3 4 5 5 -1 -1 -1 -1 -1
10 7 6 7 10
В первом примере высоты платформ после первого действия станут равны $$$1, 2, 0$$$, затем Том уменьшит их еще на $$$2$$$, и получит $$$-1, 0, -2$$$, а после последнего действия высоту станут равны $$$3, 4, 2$$$.
Во втором примере Том последовательно $$$5$$$ раз уменьшает высоты платформ на $$$1$$$. С каждым действием количество отрицательных чисел растет, поэтому ответ сначала убывает, затем возрастает. В конце высоты будут равны $$$-4, -3, -2, -1, 0$$$, что дает такой же ответ, какой получился и после первого действия, когда высоты стали равны $$$0, 1, 2, 3, 4$$$.
Том расставил по дому несколько мышеловок. Дом может быть представлен как бесконечная двумерная плоскость. Мышеловка номер $$$i$$$ находится в точке $$$(x_i, y_i)$$$.
Выпуклой оболочкой множества точек называется минимальный по площади выпуклый многоугольник (возможно, вырожденный), содержащий внутри или на границе все точки из множества.
Том считает защищенной область, соответствующую выпуклой оболочке точек, в которых расположены мышеловки.
Джерри может обезвредить ровно одну мышеловку. В результате, защищенная область уменьшится до выпуклой оболочки оставшихся мышеловок. Помогите Джерри определить, какой минимальной по площади защищенной области он может добиться.
В первой строке дано одно целое число $$$n$$$ — количество мышеловок ($$$2 \le n \le 100\,000$$$).
В следующих $$$n$$$ строках дано по два целых числа $$$x_i$$$ и $$$y_i$$$ — координаты $$$i$$$-й мышеловки ($$$|x_i|, |y_i| \le 10^9$$$). Гарантируется, что никакие две мышеловки не находятся в одной точке.
Выведите одно целое число — удвоенную площадь минимальной по площади защищенной области, которую Джерри может получить. Можно доказать, что удвоенная площадь защищенной области всегда будет целым числом.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 23 | $$$n \le 1\,000$$$ | первая ошибка | |
| 2 | 21 | Точки образуют строго выпуклый невырожденный многоугольник и даны в порядке обхода против часовой стрелки | первая ошибка | |
| 3 | 27 | Количество точек, находящихся строго внутри выпуклой оболочки, не превышает $$$10$$$ | 2 | первая ошибка |
| 4 | 29 | Без дополнительных ограничений | 1–3 | первая ошибка |
2 1 2 3 4
0
4 1 1 0 1 0 0 1 0
1
6 0 0 5 0 5 5 0 5 2 1 2 4
30
У Джерри накопилось $$$n$$$ дел, которые ему нужно сделать. Пока он будет их выполнять, он будет зарабатывать или тратить деньги. А именно, для каждого дела он знает, сколько денег он получит или потратит в момент завершения этого дела. Также известно, что Джерри не будет выполнять несколько дел одновременно, и не будет прерываться во время выполнения никакого дела.
Однако, между делами есть зависимости. Некоторые дела можно выполнять только после того, как выполнены некоторые другие необходимые дела. Каждая зависимость описывается номерами двух дел $$$a$$$ и $$$b$$$, и обозначает, что дело номер $$$b$$$ может быть выполнено только после того, как было выполнено дело номер $$$a$$$. Так как Джерри довольно хорошо спланировал свои дела, для каждой зависимости верно что $$$a \lt b \le a + 10$$$.
Джерри — ответственный, и не будет нарушать зависимости между делами. Тем не менее, он не знает точный порядок, в котором он будет выполнять дела, так как ему будет мешать Том.
Ему интересно, какое минимальное количество денег ему нужно иметь изначально, чтобы вне зависимости от того, в каком из возможных порядков он будет выполнять дела, ему гарантированно хватило денег (т.е. чтобы количество денег ни в какой момент времени не стало отрицательным).
В первой строке даны два целых числа $$$n$$$ и $$$m$$$ — количество дел, которые нужно сделать Джерри, и количество зависимостей между ними ($$$1 \le n \le 100\,000$$$, $$$1 \le m \le {10}^6$$$). В следующей строке дано $$$n$$$ целых чисел $$$c_i$$$, $$$i$$$-е из них равно величине, на которую изменится количество денег у Джерри после выполнения $$$i$$$-о дела ($$$-{10}^9 \le c_i \le {10}^9$$$).
В следующих $$$m$$$ строках дано описание зависимостей между делами. Каждая зависимость описывается парой чисел $$$a$$$ и $$$b$$$, обозначающей что дело номер $$$b$$$ можно выполнять только если уже выполнено дело номер $$$a$$$ ($$$1 \le a, b \le n$$$; $$$a \lt b \le a + 10$$$). Гарантируется, что никакая пара не встречается дважды.
Выведите одно целое неотрицательное число — минимальное количество денег, которое Джерри должен иметь изначально, чтобы вне зависимости от порядка выполнения дел, количество денег никогда не становилось отрицательным.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и всех необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 19 | $$$n \le 15$$$ | первая ошибка | |
| 2 | 16 | $$$b \le a + 1$$$ | первая ошибка | |
| 3 | 17 | Есть не более $$$10$$$ дел с отрицательным $$$c_i$$$ | первая ошибка | |
| 4 | 48 | Без дополнительных ограничений | 1, 2, 3 | первая ошибка |
4 2 1 -2 4 -3 1 2 3 4
1