В городе построили новую прямоугольную площадь размером $$$m$$$ на $$$n$$$ метров. Для освещения площади мэр хочет заказать инновационные фонари, каждый из которых освещает квадрат $$$k \times k$$$ метров, стороны которого параллельны границам площади.

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

Рассмотрим классическую игру в «Морской бой».

Согласно правилам, у каждого игрока имеется поле размера $$$10\times 10$$$ клеток, на котором он должен расставить $$$10$$$ кораблей: один «четырехпалубник» (занимает $$$1\times 4$$$ клетки), два «трехпалубника» (размера $$$1\times 3$$$ клетки), три «двухпалубника» (размера $$$1\times 2$$$ клетки) и четыре «однопалубника» (имеют размер $$$1\times 1$$$). При этом должны быть выполнены следующие условия:

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

Будем описывать расположение кораблей с помощью таблицы $$$10 \times 10$$$, где в каждом элементе находится символ '#', если соответствующая клетка занята кораблем, и '.' в противном случае. Ваша задача — по заданному полю $$$10\times 10$$$ определить, соответствует ли оно корректной расстановке кораблей, согласующейся с правилами «Морского боя».

Рене — дизайнер абстракционистских ковров. Ковры, которые создаёт Рене, представляют собой прямоугольники $$$n\times m$$$, где $$$n$$$ и $$$m$$$ — натуральные числа. Каждый ковер разделен на $$$n \times m$$$ одинаковых единичных квадратов.

Рене оформляет витрину ковров на мебельной выставке. Витрина представляет собой прямоугольную площадку со сторонами $$$h\times w$$$, где $$$h$$$ и $$$w$$$ — натуральные числа, пол на витрине также разделен на единичные квадраты.

Рене хочет, чтобы ковры были выложены на витрине аккуратно.

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

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

На одном очень скучном уроке по математике Маша нарисовала у себя в тетради неориентированный граф с $$$n$$$ вершинами и $$$m$$$ ребрами. Вершины графа были пронумерованы от $$$1$$$ до $$$n$$$.

После урока она ушла на перемену, а когда вернулась, то обнаружила, что граф, кажется, изменился!

Машин сосед по парте, Паша, признался, что в её отсутствие он немного поменял граф. А именно, он выполнял следующую операцию: взять три различных вершины графа, $$$a$$$, $$$b$$$ и $$$c$$$, и после этого для каждой пары вершин $$$(a, b)$$$, $$$(b, c)$$$ и $$$(a, c)$$$ изменить соответствующее ребро: если оно было в текущем графе, удалить его, а если его не было — провести.

Эту операцию он совершил не один, а несколько (возможно, ноль или один) раз, каждый раз заново выбирая $$$a$$$, $$$b$$$ и $$$c$$$.

Маша хочет проверить слова своего соседа, поэтому просит вас найти любую последовательность действий Паши, которая могла бы превратить исходный граф в тот, что сейчас у Маши в тетради.

В бухгалтерии гранд отеля переполох: один из гостей — Сергей, куда-то пропал и не выходит на связь, а его счет за проживание не оплачен!

Бухгалтеры гранд отеля очень ответственно относятся к своим обязанностям, поэтому для каждого посетителя заводится отдельный журнал, в котором есть 2 колонки: «услуга» и «стоимость». В графе «услуга» каждый день записываются все предоставленные отелем удобства: завтрак в постель, такси, выдача канцелярии и прочее, туда же входит и проживание в номере, которое отдельно указывается за каждый день. В графе «стоимость» напротив каждой услуги записана ее стоимость в местной валюте. Стоимость одной и той же услуги, в том числе проживания, не меняется в процессе проживания гостя.

К сожалению, из-за суматохи, вызванной исчезновением Сергея, на первую колонку журнала один из работников отеля случайно пролил чернила. По оставшейся информации известно, что Сергей жил в гранд отеле $$$n$$$ дней, а также известны стоимости $$$m$$$ услуг, предоставленных ему за все эти дни.

Поскольку Сергей — очень важный гость, у него был свой, нестандартный тариф на проживание, а чему он был равен — никто не помнит. Бухгалтерский отдел теперь хочет узнать, чему могла быть равна стоимость проживания Сергея в отеле за день.

Каждый раз когда Катя заходит в лифт, в зеркале она видит отражение номера этажа, на котором она зашла.

Номер этажа показывает табло, которое отображает цифры так, как показано на картинке.

Из-за того, что номер этажа виден в зеркале, его изображение получается отраженным относительно вертикальной оси: порядок цифр меняется на противоположный и цифры выглядят как свои отражения. При этом если цифра $$$x$$$ после отражения полностью совпадает с другой цифрой $$$y$$$, то мозг воспринимает ее как $$$y$$$, а вот если она не совпадает ни с какой другой цифрой, то, несмотря на то, что она отражена, мозг воспринимает $$$x$$$ как $$$x$$$.

Какое число увидит Катя, когда зайдет в лифт, если известно, что она живет на $$$k$$$-м этаже.

Юрик — очень занятой человек, поэтому он не успевает выполнять все необходимые дела вовремя. К концу недели у него скопилось $$$n$$$ невыполненных дел. Для удобства пронумеруем их целыми числами от $$$1$$$ до $$$n$$$. Сначала Юрик решил, что на выходных будет выполнять дела в порядке их нумерации. Однако, он быстро понял, что некоторые дела важнее других, поэтому решил изменить порядок их выполнения.

У Юрика есть любимая перестановка $$$p_1, p_2, \ldots, p_n$$$, и он решил воспользоваться ей, чтобы изменить порядок выполнения дел. Помимо того, что Юрик очень занятой человек, он также очень непостоянный, поэтому он решил изменить порядок выполнения дел $$$q$$$ раз.

Изначально Юрик записал на лист бумаги дела в том порядке, в котором он их будет выполнять: $$$1, 2, 3, \ldots, n$$$. После этого он $$$q$$$ раз выберет некоторые два числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$), после чего изменит порядок дел, которые на данный момент находятся в списке на позициях с номерами от $$$l$$$ до $$$r$$$.

Изменение порядка выполнения дел происходит следующим образом. Сначала Юрик назначает делам, которые находятся в списке на позициях с номерами от $$$l$$$ до $$$r$$$ приоритеты. Делу на позиции $$$l$$$ будет назначен приоритет $$$p_1$$$, делу на позиции $$$l + 1$$$ — приоритет $$$p_2$$$, и так далее. Таким образом, делу на позиции $$$r$$$ будет назначен приоритет $$$p_{r - l + 1}$$$. После этого Юрик переупорядочит данные дела в порядке возрастания их приоритетов. Для лучшего понимания процесса обратите внимание на пояснение к примерам.

После того, как Юрик изменил порядок выполнения дел целых $$$q$$$ раз, он окончательно запутался, и теперь хочет понять, какое дело он выполнит $$$k$$$-м по очереди. Помогите ему это выяснить.

Напомним, что перестановкой $$$p_1, p_2, \ldots, p_n$$$ называется массив попарно различных чисел от $$$1$$$ до $$$n$$$.

Во время археологических раскопок были обнаружены руины античного храма. Лучше всего сохранилась колоннада, состоящая из $$$n$$$ колонн, расположенных в ряд. Все колонны частично разрушились, поэтому оказалось, что высоты всех колонн различны. Высота $$$i$$$-й колонны равна $$$h_i$$$.

Чтобы предотвратить дальнейшее разрушение колонн из-за непогоды, было принято решение накрыть их крышами. Каждая крыша располагается горизонтально и одним концом прикрепляется к верху некоторой колонны. Можно установить крышу, которая накрывает отрезок колонн с $$$i$$$-й по $$$j$$$-ю ($$$1 \leq i \leq j \leq n$$$), если выполнено одно из следующих условий:

• Если $$$i$$$-я колонна выше всех остальных на отрезке $$$[i, j]$$$, то можно закрепить крышу левым концом на $$$i$$$-й колонне.
• Если $$$j$$$-я колонна выше всех остальных на отрезке $$$[i, j]$$$, то можно закрепить крышу правым концом на $$$j$$$-й колонне.

Наверху каждой колонны можно закрепить не более одной крыши. Стоимость закрепления крыши на $$$i$$$-й колонне равна $$$c_i$$$ вне зависимости от того, направлена она влево или вправо и сколько колонн накрывает.

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

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

Стол представляет собой прямоугольное поле из $$$n$$$ строк и $$$m$$$ столбцов. В некоторых клетках стола находятся дырки, если хотя бы одна клетка слайма окажется на дырке, он упадет со стола. Слайм занимает 4 клетки, и изначально находится в верхнем левом углу поля размером $$$2 \times 2$$$, цель его побега — занять нижний правый угол размером $$$2 \times 2$$$.

Слайм может передвигаться по полю с помощью трансформаций. Трансформация заключается в следующем: одна из клеток слайма передвигается в другую, соседнюю с ней по стороне или углу. После трансформации слайм должен образовывать 4-связную фигуру (иными словами, между любыми двумя клетками слайма должен существовать путь по клеткам слайма, переходящий каждый раз в клетку, соседнюю по стороне).

Слайм хочет сбежать от Никиты как можно быстрее, чтобы его клетки никогда не оказывались на клетках стола с дырками. Найдите минимальное число трансформаций, за которое он сможет это сделать.

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

Известно, что заводы работали $$$n$$$ дней, $$$i$$$-й из этих дней был $$$d_i$$$-м производственным днем от начала работы компании, в этот день было использовано $$$w_i$$$ сырья для производства. В остальные дни завод простаивал, будем считать, что использовалось $$$0$$$ сырья.

Производство и утилизация параметризованы коэффициентом переработки сырья $$$r$$$. Чем он выше, тем быстрее происходит утилизация, но тем больше отходов производится при обработке сырья. Формально,

• Если к концу некоторого дня на производстве ровно $$$x$$$ отходов, то в начале следующего дня их останется $$$x \cdot (1 - r)$$$.
• Если в начале дня на производстве ровно $$$x$$$ отходов, то к концу дня их станет $$$x + w \cdot r$$$, где $$$w$$$ — количество использованного в этот день сырья.

Иными словами, если к концу дня $$$j - 1$$$ на производстве $$$x$$$ отходов, а в $$$j$$$-й день используется $$$w_j$$$ сырья, к концу $$$j$$$-го дня отходов станет $$$(1 - r)x + r w_j$$$. В начале самого первого дня отходов было $$$0$$$.

Cкоро на завод приедет инспекция. Инспекцию будет интересовать информация о количестве еще не утилизированных отходов в конце каких-то дней. К сожалению, эти записи были утеряны, поэтому руководство компании просит вас помочь с ответами на вопросы инспекции, имея данные о производстве.

Василий очень любит сидеть в телефоне во время поездок в метро, и очень не любит, когда кто-то из соседей видит, чем он занимается в интернете. Вася уверен, что не единственный страдает от такой проблемы, поэтому попросил вас помочь всем любителям посидеть в одиночестве.

Рассмотрим вагон метро, в котором есть один ряд из $$$n$$$ мест, пронумерованных от $$$1$$$ до $$$n$$$, изначально все места свободны. Поступает $$$k$$$ последовательных запросов. Запросы бывают двух типов:

1. «$$$-x$$$». Ушёл пассажир, который вошёл $$$x$$$-м. Гарантируется, что такой пассажир есть в вагоне.
2. «$$$+$$$». Пришел новый пассажир. Гарантируется, что есть хотя бы одно свободное место.

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