У студента Владислава есть структура данных «мультимножество». В отличие от множества, мультимножество может содержать несколько экземпляров одного и того же элемента.

Владислав выполняет в заданном порядке $$$n$$$ операций одного из следующих двух видов:

• добавить число $$$x$$$ в мультимножество;
• удалить один экземпляр числа $$$x$$$ из мультимножества (при этом гарантируется, что число $$$x$$$ есть в мультимножестве хотя бы в единственном экземпляре).

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

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

Изначально Владислав добавил в свое множество $$$n$$$ чисел $$$a_1$$$, ..., $$$a_n$$$. Теперь он собирается $$$10^{10^{10}}$$$ раз выполнить следующую операцию: извлечь из множества минимальный элемент, и добавить в множество этот элемент, умноженный на 2.

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

Правильная скобочная последовательность определяется следующим образом:

• пустая строка — правильная скобочная последовательность;
• если $$$s$$$ — правильная скобочная последовательность, то «$$$\left(s\right)$$$» — тоже правильная скобочная последовательность;
• если $$$s$$$ и $$$t$$$ — правильные скобочные последовательности, то «$$$st$$$» — тоже правильная скобочная последовательность.

Дана скобочная последовательность. Гарантируется, что ее длина четная, а количество открывающих и закрывающих скобок в ней совпадает. За одну операцию вы можете выбрать две различные позиции $$$i$$$ и $$$j$$$, и поменять местами символы на этих позициях. За какое минимальное количество таких операций можно превратить данную скобочную последовательность в правильную?

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

Вася понимает, что писать эту строку как есть слишком рискованно, поэтому в $$$i$$$-й из следующих $$$n$$$ дней он будет записывать на заборе строку без $$$i$$$-го символа. Т. е. в первый день он запишет строку $$$s_{2}s_{3}\ldots s_{n}$$$, во второй — строку $$$s_{1}s_{3}s_{4}\ldots s_{n}$$$, а в последний, $$$n$$$-й день — строку $$$s_{1}s_{2}\ldots s_{n-1}$$$.

Сколько различных строк будет написано на заборе?

Есть трехмерное пространство из кубиков, размера $$$x \times y \times z$$$. Некоторые из этих кубиков пустые, а некоторые заполнены и образуют фигуру (не обязательно связную).

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

У вас есть $$$n$$$ монет. Вы точно знаете, что одна из них фальшивая и отличается по весу, но неизвестно, на сколько и в какую сторону.

Вы хотите c помощью серии взвешиваний определить, какая же из монет фальшивая. У вас есть весы с двумя чашами. На каждую чашу весов можно класть сколько угодно монет (но количества на первой и второй чашах должны совпадать).

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

В самом начале вашей программе сообщается единственное число $$$n$$$ ($$$3 \le n \le 1000$$$) — количество монет.

После этого вы можете сделать не более $$$9$$$ взвешиваний. Чтобы провести взвешивание, нужно вывести три строки. В первой строке должен содержаться символ «?», а затем через пробел целое положительное число $$$k$$$ — количество монет, которое вы положите на каждую чашу весов. Во второй строке должны содержаться $$$k$$$ чисел — номера монет, которые вы положите на первую чашу весов. В третьей строке аналогичным образом должны содержаться $$$k$$$ номеров монет, которые вы положите на вторую чашу весов. Все выведенные номера монет во второй и третьей строках должны быть в промежутке от $$$1$$$ до $$$n$$$ и быть различны.

В ответ на такой запрос вам приходит результат взвешивания — один из трех символов «<», «=» или «>».

После того, как вы однозначно установите фальшивую монету, выведите символ «!», а затем через пробел целое число от $$$1$$$ до $$$n$$$ — ее номер. После этого ваша программа должна завершиться.

Есть $$$n$$$ кнопок. На каждой кнопке есть дисплей, на котором отображается число. Изначально на $$$i$$$-й кнопке отображается число $$$a_i$$$. Если нажать на $$$i$$$-ю кнопку, число на ней уменьшится на $$$1$$$, а числа на всех остальных кнопках увеличатся на $$$1$$$.

Вам нужно, чтобы на $$$i$$$-й кнопке отображалось число $$$b_i$$$. Можете ли вы этого добиться, и если да, на какие кнопки надо нажимать?

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

В квартире есть $$$a$$$ односпальных и $$$b$$$ двуспальных кроватей. В делегации $$$n$$$ человек, и среди них есть люди, которые согласны спать с кем-либо вместе на двуспальной кровати, а есть люди, которые против этого.

Зная эти данные, распределите спальные места среди участников делегации.

Кирилл готовится пройти на финал ICPC. Впереди $$$n$$$ контестов, и Кирилл уже вычислил, что на $$$i$$$-м из них он сможет увеличить свой рейтинг на $$$a_i$$$. Однако после некоторых контестов Кирилл так сильно устает, что не способен участвовать в нескольких следующих. Конкретно, если он решал $$$i$$$-й контест, он должен будет пропустить как минимум следующие $$$b_i$$$ контестов.

Вычислите максимально возможное увеличение рейтинга Кирилла после $$$n$$$ контестов.

Перестановкой из $$$n$$$ элементов называется последовательность целых чисел от $$$1$$$ до $$$n$$$, в которой все числа различны.

Есть перестановка $$$p$$$ из $$$n$$$ элементов. Два игрока играют $$$q$$$ раундов в следующую игру: они одновременно называют случайное число от $$$1$$$ до $$$n$$$ (если их числа совпадают, они делают это еще раз, пока их числа не окажутся различными), а побеждает тот игрок, чье число встречается в перестановке $$$p$$$ раньше.

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

Деревом называется связный граф без циклов. Количество ребер в дереве всегда на 1 меньше, чем количество вершин.

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

Какое минимальное количество раз придется телепортироваться, чтобы выполнить свой план?

Есть две строки $$$s$$$ и $$$t$$$. Разрешается любое количество раз выполнять следующую операцию: выбрать две позиции $$$i$$$ и $$$j$$$ в строке $$$s$$$ ($$$i \lt j$$$), и перевернуть подстроку $$$s_{i\ldots j}$$$. Т. е. $$$i$$$-й символ поменяется местами с $$$j$$$-м, $$$\left(i+1\right)$$$-й с $$$\left(j-1\right)$$$-м, и т. д.

Можно ли с помощью таких операций превратить $$$s$$$ в $$$t$$$?

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

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

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

Даны 4 точки. Найдите, сколько из них лежат на границе их выпуклой оболочки.