В галактике находится n планет, на каждой из которых обитают множество различных живых существ. И каждое из них может оказаться в беде! Космические спасатели прекрасно знают об этом и всегда готовы помочь каждому, кому эта помощь действительно понадобится. Стоит только позвать.

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

Поскольку планеты достаточно удалены друг от друга, их можно считать точками в евклидовом трехмерном пространстве. Расстояние между точками (x_i, y_i, z_i) и (x_j, y_j, z_j) вычисляется по формуле . Спасательная база может располагаться в любой точке пространства, в том числе, совпадать с какой либо из планет.

Галактика в опасности! Спасите космических спасателей и укажите им искомую точку.

Вам дан набор точек \(x_1\), \(x_2\), ..., \(x_n\) на числовой прямой.

Две точки \(i\) и \(j\) могут быть соединены друг с другом при выполнении следующих условий:

• Ни \(i\), ни \(j\) не соединены ни с какими другими точками;
• \(|x_i - x_j| \ge z\).

Какое максимальное количество пар точек вы можете соединить друг с другом?

Это — упрощённая версия задачи. В этой версии, \(1 \le n \le 10^5\) и \(0 \le a_i \le 1\). Вы можете взламывать эту задачу только тогда, когда решите и заблокируете обе версии.

Приближается Рождество, и наш главный герой, Боб, готовит эффектный подарок для своей давней лучшей подруги Алисы. В этом году он решил приготовить \(n\) коробок шоколада, пронумерованных от \(1\) до \(n\). Изначально \(i\)-я коробка содержит \(a_i\) кусочков шоколада.

Поскольку Боб — типичный приятный парень, он не отправит Алисе \(n\) пустых ящиков. Другими словами, минимум одно число из \(a_1, a_2, \ldots, a_n\) является положительным. Поскольку Алиса не любит взаимно простые множества, она будет счастлива, только если существует какое-то целое число \(k > 1\), такое, что количество кусочков в каждой коробке делится на \(k\). Обратите внимание, что Алиса не будет возражать, если будут какие-то пустые коробки.

Чарли, парень Алисы, также является вторым лучшим другом Боба, поэтому он решает помочь Бобу, переставляя кусочки шоколада. За одну секунду Чарли может взять кусок в \(i\)-й коробке, и поместить его либо в \(i-1\)-ю коробку или \(i+1\)-ю коробку (если такие коробки существуют). Конечно, он хочет помочь своему другу как можно быстрее. Поэтому он просит вас подсчитать минимальное количество секунд, которое понадобится ему, чтобы сделать Алису счастливой.

Адилбеку назначили особый проект. Для Адилбека это означает, что у него есть \(n\) дней, чтобы запустить особую программу и представить полученные результаты. Но есть одна проблема: программе нужно работать \(d\) дней, чтобы посчитать результаты.

К счастью, Адилбек может оптимизировать программу. Если он потратит \(x\) (\(x\) — целое неотрицательное) дней на оптимизацию, то программа станет работать за \(\left\lceil \frac{d}{x + 1} \right\rceil\) дней (\(\left\lceil a \right\rceil\) — это округление вверх: \(\left\lceil 2.4 \right\rceil = 3\), \(\left\lceil 2 \right\rceil = 2\)). Программу не получится оптимизировать, пока она работает, а потому общее количество потраченных Адилбеком дней будет равняться \(x + \left\lceil \frac{d}{x + 1} \right\rceil\).

Успеет ли Адилбек получить результаты за не более, чем \(n\) дней?

Представим следующий алгоритм. Есть массив \(v_1, v_2, \dots, v_n\), изначально заполненный нулями. Несколько раз с массивом проделываются похожие операции — на \(i\)-м шаге (в \(0\)-индексации) вы можете:

• либо выбрать любую позицию \(pos\) (\(1 \le pos \le n\)) и увеличить \(v_{pos}\) на \(k^i\);
• либо не выбирать позицию и пропустить шаг.

Вы можете выбирать, как алгоритм ведет себя на каждом шаге и когда он будет остановлен. Вопрос в следующем: можно ли сделать массив \(v\) равным некоторому массиву \(a\) (\(v_j = a_j\) для каждого \(j\)) после некоторого шага?

Условие этой задачи почти полностью совпадает с условием задачи C2. Единственное отличие в следующем: в задаче C1 \(n\) всегда четно, а в задаче C2 \(n\) всегда нечетно.

Вам задан правильный многоугольник из \(2 \cdot n\) вершин (то есть он выпуклый и имеет равные стороны и углы) и все его стороны имеют длину \(1\). Назовем этот многоугольник \(2n\)-угольником.

Ваша задача — найти квадрат минимального размера, такой что в него можно вписать \(2n\)-угольник. \(2n\)-угольник можно вписать в квадрат, если \(2n\)-угольник можно разместить таким образом, что каждая точка, лежащая внутри или на границе \(2n\)-угольника также будет лежать внутри или на границе квадрата.

Вы можете вращать \(2n\)-угольник и/или квадрат.

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

Летние каникулы начались, поэтому Алиса и Боб хотят играть и веселиться, но... Их мама не согласна с этим. Она говорит, что они должны прочитать ровно \(m\) книг перед всеми развлечениями. Алиса и Боб прочитают каждую книгу вместе, чтобы быстрее закончить это задание.

В семейной библиотеке есть \(n\) книг. \(i\)-я книга характеризуется тремя целыми числами: \(t_i\) — количество времени, которое Алиса и Боб должны потратить, чтобы прочитать ее, \(a_i\) (равное \(1\), если Алисе нравится \(i\)-я книга, и \(0\), если не нравится), и \(b_i\) (равное \(1\), если Бобу нравится \(i\)-я книга, и \(0\), если не нравится).

Поэтому им нужно выбрать ровно \(m\) книг из имеющихся \(n\) книг таким образом, что:

• Алисе нравятся не менее \(k\) книг из выбранного множества и Бобу нравятся не менее \(k\) книг из выбранного множества;
• общее время, затраченное на прочтение этих \(m\) книг минимизировано (ведь они дети и хотят начать играть и веселиться как можно скорее).

Множество, которое они выбирают, одинаковое и для Алисы и для Боба (они читают одни и те же книги), и они читают все книги вместе, таким образом, суммарное время чтения равно сумме \(t_i\) по всем книгам, которые находятся в выбранном множестве.

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

Boboniu определяет BN-строку как строку \(s\) из символов 'B' и 'N'.

Он может совершать следующие операции над BN-строкой \(s\):

• Удалить один символ из \(s\).
• Удалить подстроку «BN» или «NB» из \(s\).
• Добавить символ 'B' или 'N' в конец \(s\).
• Добавить строку «BN» или «NB» в конец \(s\).

Строка \(a\) является подстрокой строки \(b\) если \(a\) может быть получена из \(b\) удалением нескольких (возможно, нуля или всех) символов из начала и нескольких (возможно, нуля или всех) символов из конца.

Boboniu считает, что BN-строки \(s\) и \(t\) похожи если и только если:

• \(|s|=|t|\).
• Существует перестановка \(p_1, p_2, \ldots, p_{|s|}\), что для всех \(i\) (\(1\le i\le |s|\)), \(s_{p_i}=t_i\).

Boboniu также определяет \(\text{dist}(s,t)\), расстояние между \(s\) и \(t\), как минимальное число операций, необходимое чтобы сделать \(s\) похожей на \(t\).

Теперь Boboniu дал вам \(n\) непустых BN-строк \(s_1,s_2,\ldots, s_n\) и просит вас найти непустую BN-строку \(t\), что максимальное расстояние до строки из \(s\) минимизировано, т.е. вам нужно минимизировать \(\max_{i=1}^n \text{dist}(s_i,t)\).

Заключенный хочет сбежать из тюрьмы. Тюрьма является внутренней частью выпуклого многоугольника с вершинами \(P_1, P_2, P_3, \ldots, P_{n+1}, P_{n+2}, P_{n+3}\). Известно, что \(P_1=(0,0)\), \(P_{n+1}=(0, h)\), \(P_{n+2}=(-10^{18}, h)\) и \(P_{n+3}=(-10^{18}, 0)\).

Стены тюрьмы \(P_{n+1}P_{n+2}\), \(P_{n+2}P_{n+3}\) и \(P_{n+3}P_1\) очень высокие, и заключенный не может на них взобраться. Следовательно, его единственный шанс  — это достичь точки на одной из стен \(P_1P_2, P_2P_3,\dots, P_{n}P_{n+1}\) и сбежать оттуда. По периметру тюрьмы находятся два охранника. Заключенный движется со скоростью \(1\), в то время как охранники движутся, всегда оставаясь на периметре тюрьмы, со скоростью \(v\).

Если заключенный достигает точки на периметре, где есть охранник, охранник убивает заключенного. Если заключенный достигает точки, на которую он может взобраться, и там нет охранника, то он сразу же убегает. Изначально заключенный находится в точке \((-10^{17}, h/2)\), а охранники  — в точке \(P_1\).

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

Замечания:

• В любой момент охрана и заключенный могут видеть друг друга.
• Залезание на стену не занимает времени.
• Вы можете считать, что и заключенный, и охранники могут изменить направление и скорость мгновенно и что они оба имеют идеальные рефлексы (так что они могут мгновенно реагировать на то, что делает другой).
• Оба охранника могут заранее спланировать, как реагировать на передвижения заключенного.

Это интерактивная задача.

Гомеру очень нравятся массивы, и он хочет поиграть с вами в игру. Гомер загадал перестановку \(a_1, a_2, \dots, a_n\) чисел от \(1\) до \(n\). Вас просят найти любой индекс \(k\) (\(1 \leq k \leq n\)), который является локальным минимумом.

Для массива \(a_1, a_2, \dots, a_n\) индекс \(i\) (\(1 \leq i \leq n\)) считается локальным минимумом, если \(a_i < \min\{a_{i-1},a_{i+1}\}\), где \(a_0 = a_{n+1} = +\infty\). Массив называется перестановкой чисел от \(1\) до \(n\), если он содержит все целые числа от \(1\) до \(n\) ровно один раз.

Изначально вам дается только значение \(n\) без какой-либо другой информации об этой перестановке. На каждом шаге взаимодействия вы можете выбрать любой индекс \(i\) (\(1 \leq i \leq n\)) и сделать с ним запрос. В ответ вы получите значение \(a_i\).

Вы должны найти любой индекс \(k\), который является локальным минимумом, за не более чем \(100\) запросов.

Вы начинаете взаимодействие с чтения целого числа \(n\) (\(1\le n \le 10^5\)) в отдельной строке.

Чтобы сделать запрос с индексом \(i\) (\(1 \leq i \leq n\)), необходимо в отдельной строке вывести «? \(i\)». Затем считайте в отдельной строке значение \(a_i\). Количество запросов «?» должно не превышать \(100\).

Чтобы вывести индекс \(k\) (\(1 \leq k \leq n\)), который является локальным минимумом, выведите «! \(k\)» в отдельной строке и завершите вашу программу.

В случае, если ваш запрос имеет неверный формат, или вы сделали более \(100\) запросов типа «?», вы получите вердикт Неправильный ответ.

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

Формат взломов

Первая строка взлома должна содержать единственное целое число \(n\) (\(1 \leq n \leq 10^5\)).

Вторая строка должна содержать попарно различные целые числа \(n\) \(a_1, a_2, \dots, a_n\) (\(1 \leq a_i \leq n\)).

Дана последовательность \(A\), в которой каждый элемент записан в формате + x или -, где \(x\) — целое число.

Для последовательности \(S\), в которой каждый элемент записан в формате + x или -, определим \(f(S)\) следующим образом:

• Проходим по \(S\) от первого элемента до последнего и поддерживаем мультимножество \(T\), изначально пустое.
• Если элемент последовательности имеет вид + x, добавим \(x\) в \(T\). Иначе удалим наименьший элемент из \(T\) (если \(T\) пусто, ничего делать не нужно).
• После прохода по \(S\) посчитаем сумму всех элементов в \(T\). \(f(S)\) полагается равным этой сумме.

Последовательность \(b\) является подпоследовательностью последовательности \(a\), если \(b\) может быть получена из \(a\) удалением нуля или больше элементов без изменения порядка оставшихся элементов. Для всех подпоследовательностей \(B\) последовательности \(A\) посчитайте сумму \(f(B)\) по модулю \(998\,244\,353\).

Little Johnny Bubbles enjoys spending hours in front of his computer playing video games. His favorite game is Bubble Strike, fast-paced bubble shooting online game for two players.

Each game is set in one of the N maps, each having different terrain configuration. First phase of each game decides on which map the game will be played. The game system randomly selects three maps and shows them to the players. Each player must pick one of those three maps to be discarded. The game system then randomly selects one of the maps that were not picked by any of the players and starts the game.

Johnny is deeply enthusiastic about the game and wants to spend some time studying maps, thus increasing chances to win games played on those maps. However, he also needs to do his homework, so he does not have time to study all the maps. That is why he asked himself the following question: "What is the minimum number of maps I have to study, so that the probability to play one of those maps is at least \(P\)"?

Can you help Johnny find the answer for this question? You can assume Johnny's opponents do not know him, and they will randomly pick maps.

Задано поле, состоящее из \(2\) строк и \(m\) столбцов. Строки занумерованы от \(1\) до \(2\) сверху вниз. Столбцы занумерована от \(1\) до \(m\) слева направо.

Робот начинает в клетке \((1, 1)\). За одну секунду он может проделать любое из двух действий:

• перейти в соседнюю по стороне клетку: наверх, направо, вниз или налево;
• остаться в той же клетке.

Роботу запрещено выходить за пределы поля.

Изначально все клетки, кроме клетки \((1, 1)\) заблокированы. Каждая клетка \((i, j)\) содержит значение \(a_{i,j}\) — момент, когда данная клетка будет разблокирована. Робот может перейти в клетку \((i, j)\), если до начала хода прошло хотя бы \(a_{i,j}\) секунд.

Робот должен посетить все клетки, не входя ни в какую клетку дважды или больше (считается, что робот вошел в клетку \((1, 1)\) на старте). Он может закончить в любой клетке.

Какое минимальное время у него это может занять?

Единственная разница между этой задачей и сложной версией — максимальное количество вопросов.

Это интерактивная задача!

Загадано некоторое целое число \(1 \le x \le n\), которое вам нужно найти. Чтобы найти его, вы можете задать не более \(\mathbf{82}\) вопросов.

В каждом вопросе вы можете выбрать непустое множество целых чисел \(S\) и спросить, принадлежит ли \(x\) множеству \(S\) или нет. После каждого запроса, если \(x\) принадлежит \(S\), вы получите «YES», иначе «NO».

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

Вы также можете сделать не более \(2\) попыток угадать \(x\). Каждый раз, если вы правильно угадаете \(x\), вы получите «:)» и ваша программа должна завершиться, иначе вы получите «:(».

Как часть шутки, мы не будем фиксировать значение \(x\) в начале. Наоборот, это значение может изменяться в процессе взаимодействия, но все уже полученные ответы всегда будут корректны с точки зрения описанного выше.

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

Для каждого вопроса, если вы хотите спросить о множестве \(S\), сначала выведите символ «?», затем выведите размер множества \(S\), а затем уже элементы \(S\) один за другим. Все элементы должны быть различными целыми числами от \(1\) до \(n\). После каждого вопроса вы получите ответ на него: «YES» или «NO» в соответствии с условием. Вы можете задать не более \(82\) таких запросов.

Если вы хотите угадать \(x\), сначала выведите «!», а затем выведите свою догадку. Если вы угадаете \(x\) правильно, вы получите «:)» и ваша программа должна завершиться, иначе вы получите «:(». Вы можете сделать не более \(2\) таких догадок.

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

Взломы в этой задаче отключены.

Как известно, во всей вселенной принята трёхмерная декартова система координат, в которой каждой точке ставится в соответствие три вещественные координаты (x, y, z). В этой системе координат, расстояние от центра вселенной до точки считается по формуле: . Грибные ученые, подчиненные Великого Грибного короля, считают, что вселенная не совсем права и что расстояние от центра вселенной до точки равно x^a·y^b·z^c.

Чтобы «завалить» метрику грибных ученых, обычные учёные задали им задачку: найти такие x, y, z (0 ≤ x, y, z; x + y + z ≤ S), что расстояние от центра вселенной до точки (x, y, z) в метрике грибных ученых максимально. Грибные ученые не сильны в математике, поэтому они поручили это задание Вам.

Обратите внимание, в этой задаче считается, что 0⁰ = 1.

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

Армия жителей Средиземья будет состоять из нескольких отрядов. Известно, что каждая пара существ одной расы, которые находятся в разных отрядах, прибавляет \(b\) единиц к суммарной силе армии. Но так как Тимофею будет сложно руководить армией, состоящей из большого числа отрядов, то суммарная сила армии, состоящей из \(k\) отрядов, уменьшается на \((k - 1) \cdot x\) единиц. Обратите внимание, что армия всегда состоит из хотя бы одного отряда.

Известно, что в Средиземье проживают \(n\) рас, и количество существ \(i\)-й расы равно \(c_i\). Помогите жителям Средиземья определить максимальную силу армии, которую они могут составить.

Боб решил открыть булочную. В день открытия он испёк \(n\) булок, которые может продать. Обычная цена булки равна \(a\) монет, но чтобы привлечь покупателей, Боб организовал следующую акцию:

• Боб выбирает некоторое целое число \(k\) (\(0 \le k \le \min(n, b)\)).
• Первые \(k\) булок Боб продаёт по изменённой цене. В таком случае цена \(i\)-й (\(1 \le i \le k\)) проданной булки равна \((b - i + 1)\) монет.
• Оставшиеся \((n - k)\) булок Боб продаёт по \(a\) монет за каждую.

Обратите внимание, что \(k\) может равняться \(0\). В таком случае Боб продаст все булки по \(a\) монет за каждую.

Помогите Бобу определить максимальную прибыль, которую он может получить, если продаст все \(n\) булок.

Это сложная версия задачи. Единственное отличие между двумя версиями заключается в том, что в этой версии вы можете сделать не более \(\mathbf{7}\) запросов.

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

У нас есть секретная линейка, на которой отсутствует одно число \(x\) (\(2 \leq x \leq 999\)). Когда вы измеряете объект длиной \(y\), линейка сообщает следующие значения:

• Если \(y < x\), линейка (правильно) измеряет объект как имеющий длину \(y\).
• Если \(y \geq x\), линейка неправильно измеряет объект как имеющий длину \(y+1\).

Линейка выше не имеет числа \(4\), поэтому она правильно измеряет первый отрезок как длину \(3\), но неправильно измеряет второй отрезок как длину \(6\), хотя на самом деле он равен \(5\).

Вам нужно найти значение \(x\). Для этого вы можете делать запросы следующего вида:

• \(\texttt{?}~a~b\) — в ответ мы измерим стороны прямоугольника \(a \times b\) с помощью нашей линейки и умножим результаты, сообщив вам измеренную площадь прямоугольника. Например, если \(x=4\) и вы запрашиваете прямоугольник \(3 \times 5\), мы измерим его стороны как \(3 \times 6\) и сообщим вам \(18\).

Найдите значение \(x\). Вы можете задать не более \(\mathbf{7}\) запросов.

Для каждого набора нет начального ввода. Вы должны начать взаимодействие, задав запрос.

Чтобы сделать запрос, выведите одну строку формата \(\texttt{?}~a~b\) (\(1 \leq a, b \leq 1000\)). В ответ вам будет сообщена измеренная площадь прямоугольника согласно нашей секретной линейке.

Когда вы будете готовы вывести ответ, выведите одну строку формата \(\texttt{!}~x\) (\(2 \leq x \leq 999\)). После этого продолжайте обрабатывать следующий набор или завершите программу, если это был последний набор. Печать ответа не считается запросом.

Интерактор не адаптивен, что означает, что ответ известен до того, как участник задаст запросы, и не зависит от запросов, заданных участником.

Если ваша программа сделает более \(7\) запросов для одного набора входных данных, сделает недопустимый запрос или выведет неправильное значение \(x\), то ответ на запрос будет \(-1\). После получения такого ответа ваша программа должна немедленно завершиться, чтобы получить вердикт Неправильный ответ. В противном случае вы можете получить произвольный вердикт, поскольку ваше решение продолжит чтение из закрытого потока.

После вывода запроса не забудьте вывести конец строки и сбросить вывод. В противном случае вы можете получить вердикт Превышен лимит бездействия. Для этого используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

Взломы

Чтобы сделать взлом, используйте следующий формат.

Первая строка должна содержать одно целое число \(t\) (\(1 \leq t \leq 1000\)) — количество наборов входных данных.

Единственная строка каждого набора должна содержать одно целое число \(x\) (\(2 \leq x \leq 999\)) — отсутствующее число на линейке.

У Кли есть массив \(a\) длиной \(n\), содержащий целые числа \([k, k+1, ..., k+n-1]\) в этом порядке. Кли хочет выбрать индекс \(i\) (\(1 \leq i \leq n\)) так, чтобы \(x = |a_1 + a_2 + \dots + a_i - a_{i+1} - \dots - a_n|\) был минимален. Обратите внимание, что для произвольного целого числа \(z\), \(|z|\) представляет собой модуль числа \(z\).

Выведите минимально возможное значение \(x\).

Даны три неотрицательных целых числа \(b\), \(c\) и \(d\).

Найдите неотрицательное целое число \(a \in [0, 2^{61}]\), такое что \((a\, |\, b)-(a\, \&\, c)=d\), где \(|\) и \(\&\) обозначают операцию побитового ИЛИ и операцию побитового И соответственно.

Если такое \(a\) существует, выведите его значение. Если решения не существует, выведите одно целое число \(-1\). Если существует несколько решений, выведите любое из них.

Вы сражаетесь с монстром со здоровьем \(z\), используя оружие с уроном \(d\). Изначально \(d=0\). Вы можете выполнять следующие действия.

• Увеличить \(d\) — урон вашего оружия на \(1\), потратив \(x\) монет.
• Атаковать монстра, нанеся ему \(d\) урона, потратив \(y\) монет.

Вы не можете выполнять первую операцию более \(k\) раз подряд.

Найдите минимальное количество монет, необходимое для того, чтобы победить монстра, нанеся ему хотя бы \(z\) урона.

На плоскости есть \(n+m\) различных точек \((a_1,0), (a_2,0), \ldots, (a_{n},0), (b_1,2), (b_2,2), \ldots, (b_{m},2)\). Изначально ваш счет равен \(0\). Чтобы увеличить свой счет, вы можете выполнить следующую операцию:

• Выберите три различные точки, которые не лежат на одной прямой.
• Увеличьте свой счет на площадь треугольника, образованного этими тремя точками.
• Затем удалите три точки с плоскости.

Пример игры, где операция выполняется дважды.

Пусть \(k_{\max}\) — максимальное количество операций, которое можно выполнить. Например, если нельзя выполнить эту операцию ни разу, то \(k_\max\) равно \(0\). Кроме того, определим \(f(k)\) как максимальный возможный счет, который можно получить, выполнив операцию ровно \(k\) раз. Здесь \(f(k)\) определено для всех целых чисел \(k\), таких что \(0 \le k \le k_{\max}\).

Найдите значение \(k_{\max}\) и найдите значения \(f(x)\) для всех целых чисел \(x=1,2,\ldots,k_{\max}\) независимо.

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

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

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

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

Деву и его братишка очень любят друг друга. Они супер-гики и предпочитают играть только с массивами. Как-то раз папа подарил им два массива, a и b. Массив a достался Деву, а b — его брату.

Деву — пакостник тот еще. Хочется ему, чтобы минимум в массиве a был не меньше максимума массива b.

Вам надо помочь Деву добиться описанного. Для этого вы можете выполнять операции с массивами a и b. За одну операцию разрешено уменьшить или увеличить любой элемент любого массива на 1. Обратите внимание, что операцию можно применять несколько раз для любого элемента любого массива.

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

После скобочных последовательностей Артур увлекся теорией чисел. И у него появилась новая любимая последовательность длины n (a₁, a₂, ..., a_n), состоящая из целых чисел, и целое число k, не превышающее n.

Эта последовательность обладала следующим свойством. Если выписать суммы всех ее подотрезков, состоящих из k подряд идущих элементов (a₁  +  a₂ ...  +  a_k,  a₂  +  a₃  +  ...  +  a_k + 1,  ...,  a_{n - k + 1}  +  a_{n - k + 2}  +  ...  +  a_n), то элементы выписанной последовательности будут строго возрастать.

Например, для следующего примера: n = 5,  k = 3,  a = (1,  2,  4,  5,  6) последовательность сумм будет иметь вид: (1  +  2  +  4,  2  +  4  +  5,  4  +  5  +  6) = (7,  11,  15), а значит последовательность a удовлетворяет описанному свойству.

Очевидно, в последовательности сумм будет n - k + 1 элемент.

Кто-то (не будем говорить кто) заменил в последовательности Артура некоторые числа на знаки вопроса (если число заменяется, то ровно на один знак вопроса). Нужно восстановить последовательность, чтобы она удовлетворяла нужному свойству, и при этом минимизировать сумму |a_i|, где |a_i| — абсолютная величина a_i.

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

Более формально, будем считать Петину машину многоугольником на плоскости. Тогда после включения она проедет круг вокруг некоторой точки, к которой Петя её привязал (эта точка находится строго снаружи многоугольника). Таким образом каждая точка внутри или на границе многоугольника пройдёт по окружности с центром в точке, к которой Петя привязал свою машину.

Петя решил привязать свою машину к точке P, и теперь ему интересно, какова площадь области, с которой машина уберёт снег. Помогите ему.

Лимак — старый бурый медведь. Он часто играет в боулинг со своими друзьями. Сегодня он в отличном настроении и хочет побить свой собственный рекорд!

За каждый бросок даётся некоторое целое (возможно отрицательное) количество очков. Очки за i-й бросок умножаются на число i и прибавляются к общей сумме. Таким образом, за k бросков с очками s₁, s₂, ..., s_k в сумме даётся очков. Если бросков не было, общее количество очков равно 0.

Лимак сделал n бросков и получил a_i очков за i-й бросок. Он хочет максимизировать общее количество очков, поэтому ему в голову пришла интересная идея. Он может сказать, что некоторое количество первых бросков он разогревался и был рассредоточен во время некоторого количества последних бросков. Формально он может выкинуть некоторый префикс и некоторый суффикс последовательности очков a₁, a₂, ..., a_n. Разрешается выкидывать из рассмотрения все броски или же не выкидывать из вовсе.

Общее количество очков вычисляется как будто выкинутых бросков не было. Таким образом, за первый невыкинутый бросок количество очков умножается на 1, за второй — на 2 и так далее до последнего невыкинутого броска.

Какое максимальное количество очков может получить Лимак?

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

Как и всегда, этим утром Петя собрался на рынок. У Пети дома стоит n различных сувениров; i-й сувенир характеризуется своим весом w_i и стоимостью c_i. По предыдущим дням Петя понял, что, скорее всего, ему не удастся донести все сувениры до рынка. Поэтому Петя хочет выбрать такое подмножество сувениров, что суммарный вес всех сувениров из подмножества не превышает m, а суммарная стоимость максимальна.

Помогите Пете определить максимальную суммарную стоимость.

Проходит очередной финал Start[c]up, поэтому необходимо заказать пиццу для финалистов, участвующих в соревновании в офисе компании. Существует всего два типа пиццы (конечно нет, но в этой задаче будем считать, что да), все пиццы содержат одинаковое число S кусочков.

Известно, что i-й участниц съест s_i кусочков пиццы, и получит a_i единиц счастья от съедания каждого кусочка пиццы первого типа, и b_i единиц счастья от съедания каждого кусочка пиццы второго типа. Мы можем заказать любое число пицц первого и второго типов, но мы хотим заказать минимальное число пицц, необходимое для того, чтобы все участники могли съесть необходимое каждому число кусочков. Учитывая это ограничение, какое максимальное суммарное число единиц счастья могут получить участники?

В Тридевятом царстве — Тридесятом государстве живет один очень необычный обитатель — Дварф (а на Руси — просто Гном) Гракула. Однако необычное имя — не главная его странность (тем более, что местные жители с незапамятных времен кличут его Гномом Гришей). Главные странности состоят в том, что живет Гном Гриша уже более 200 лет, причем живет он в склепе на заброшенном кладбище, и днем его еще никто ни разу не видел. Так же точно, как никто не видел, что Гном Гриша покупает себе еду. Поэтому никто особо не удивился, когда после трагической гибели Змея Горыныча с лугов не перестал пропадать скот — местные жители давно были убеждены, что причина пропаж — совсем не безобидный Горыныч, который давно признавался, что склонен к вегетарианству. Но самое плохое во всей этой истории даже не это.

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

Вы формализовали задачу на плоскости следующим образом: пусть ширина коридора до и после поворота равна соответственно a и b (см. рисунок), коридор поворачивает строго под прямым углом, гроб суть прямоугольник с длиной и шириной соответственно l и w (l ≥ w). Гном Гриша уже определил длину гроба (l), исходя из своего роста, ваша задача — определить максимально возможную ширину гроба (w), при которой его можно будет внести в склеп. При этом в силу большой массы (чистый мрамор!) гроб оснащен вращающимися колесиками, поэтому его невозможно оторвать от земли, однако он может совершать произвольные перемещения и вращения в рассматриваемой плоскости. Гроб разрешено развернуть произвольным образом и до внесения в склеп и перемещения по коридору.

Гриша пообещал, что если вы поможете ему — он наградит вас бессмертием (интересно, как?), а если нет — то лучше вам не знать, что произойдет...