Пандемия охватила все страны мира, и Берляндия не стала исключением. Даже на Всеберляндской олимпиаде по информатике были введены противовирусные меры.

Всего в олимпиаде участвуют $$$n$$$ человек, и, чтобы соблюсти все предписания руководства, жюри олимпиады решило приглашать участников на тур по одному с интервалом $$$x$$$ минут. Таким образом первый участник начнёт тур в момент времени $$$0$$$, второй участник начнёт тур в момент времени $$$x$$$, третий — в момент времени $$$2 \cdot x$$$ и так далее.

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

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

В данной задаче $$$20$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$5$$$ баллов. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.

Решения, корректно работающие при $$$n, x, t \le 10$$$, наберут не менее $$$25$$$ баллов.

Решения, корректно работающие при $$$n \le 1000$$$, наберут не менее $$$50$$$ баллов.

Решения, корректно работающие при $$$n \le 100\,000$$$, наберут не менее $$$75$$$ баллов.

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

Однажды Петя в очередной раз написал грустную песню про любовь и поспешил показать ее Васе. Песня представляет собой строку из маленьких букв английского алфавита. У Васи сразу возникло $$$q$$$ вопросов про эту песню. Каждый вопрос представляет собой некоторый отрезок песни с позиции $$$l$$$ до позиции $$$r$$$ включительно. Вася рассматривает подстроку, образованную символами на этом отрезке, а затем повторяет каждую букву в этой подстроке $$$k$$$ раз, где $$$k$$$ — порядковый номер соответствующей буквы в алфавите. Например, если Вася выбрал подстроку «abbcb», то он повторит букву «a» один раз, каждую из букв «b» — по два раза, букву «c» — три раза, и полученная строка будет равна «abbbbcccbb», ее длина равна 10. Вася интересуется именно длиной полученной строки.

Помогите Пете ответить Васе на его вопросы, а именно, для каждого из заданных вопросов определите длину строки, которую выпишет Вася.

В данной задаче $$$20$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$5$$$ баллов. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.

Решения, корректно работающие при $$$n, q \le 1000$$$, наберут не менее $$$25$$$ баллов.

Решения, корректно работающие при $$$n, q \le 10\,000$$$, наберут не менее $$$50$$$ баллов.

Решения, корректно работающие в случае, когда $$$s$$$ состоит из символов $$$a,b$$$, наберут не менее $$$25$$$ баллов.

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

Есть $$$n$$$ учеников, пронумерованных от $$$1$$$ до $$$n$$$. Уровень знаний $$$i$$$-го ученика равен $$$a_i$$$. Всех учеников нужно распределить на стабильные параллели. Параллель называется стабильной, если после сортировки всех учеников параллели в порядке возрастания их уровня знаний у любых двух подряд идущих учеников разница уровня знаний не превосходит $$$x$$$.

Преподаватели достаточно находчивые люди, поэтому они могут пригласить не более $$$k$$$ дополнительных учеников с любым требуемым уровнем знаний. Определите минимальное число стабильных параллелей, на которые можно распределить всех учеников (возможно, пригласив не более $$$k$$$ новых учеников).

В данной задаче $$$50$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$2$$$ балла. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.

Решения, корректно работающие при $$$n, k, x, a_i \le 10$$$, наберут не менее $$$20$$$ баллов.

Решения, корректно работающие при $$$k = 0$$$, наберут не менее $$$14$$$ баллов.

Решения, корректно работающие, когда ответ не превосходит $$$2$$$, наберут не менее $$$16$$$ баллов.

Решения, корректно работающие при $$$n, k, x, a_i \le 1000$$$, наберут не менее $$$40$$$ баллов.

Девочка Лена — самая экономная девочка в Москве. Поэтому когда папа поручил ей закупку продуктов для поездки на дачу, она сразу отправилась в самый лучший магазин — «PriceFixed». У этого магазина есть несколько особенностей:

• В магазине есть бесконечный запас каждого товара.
• Все товары в нем стоят одинаково — ровно 2 рубля.
• Для каждого из $$$i$$$ товаров предусмотрена скидка для опытных покупателей: если вы уже приобрели $$$b_i$$$ товаров (любого типа, не обязательно типа $$$i$$$), то на все последующие покупки $$$i$$$-го товара будет действовать скидка $$$50\%$$$ (то есть, $$$i$$$-й товар можно будет покупать за 1 рубль!).

Лене нужно купить $$$n$$$ товаров: $$$i$$$-го товара нужно купить $$$a_i$$$ штук. Помогите Лене понять, какую минимальную сумму денег ей нужно будет потратить, если она будет выбирать порядок покупки товаров оптимальным образом.

В данной задаче $$$20$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$5$$$ баллов. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.

Обозначим за $$$A$$$ сумму по всем $$$a_i$$$ в тесте.

Решения, корректно работающие при $$$n, A \le 8$$$, наберут не менее $$$20$$$ баллов.

Решения, корректно работающие при $$$n, A \le 15$$$, наберут не менее $$$40$$$ баллов.

Решения, корректно работающие при $$$n, A \le 1000$$$, наберут не менее $$$60$$$ баллов.

Решения, корректно работающие при $$$n, A \le 100\,000$$$, наберут не менее $$$80$$$ баллов.

Алиса и Боб играют в очень интересную карточную игру. На каждой карте в этой игре написано одно целое число. На протяжении игры у Боба в каждой из двух рук находится ровно одна карта. Изначально Боб держит в левой руке карту с числом 0, а в правой руке — также карту с числом 0.

Алиса делает $$$n$$$ ходов. На ходу с номером $$$i$$$ она предлагает Бобу карту с числом $$$k_i$$$, а также 4 числа $$$a_i$$$, $$$b_i$$$, $$$c_i$$$, $$$d_i$$$. Боб выбирает, в какую руку он хочет взять новую карту, после чего выбрасывает карту из этой руки и берет в эту руку новую карту Алисы. После этого Алиса проверяет карты Боба. А именно, пусть он в левой руке держит карту $$$x$$$, а в правой — карту $$$y$$$. Тогда должно выполняться $$$a_i \le x \le b_i$$$ и $$$c_i \le y \le d_i$$$, иначе игра немедленно заканчивается.

Боб заранее знает все числа $$$k_i$$$, $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ и $$$d_i$$$. Помогите ему выбрать для каждого хода, в левую или правую руку ему следует класть очередную карту, чтобы в итоге все условия Алисы были выполнены.

Тесты к этой задаче состоят из 6 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп.

У Васи есть массив, состоящий из $$$n$$$ чисел $$$a_1, a_2, \ldots, a_n$$$. Для каждой позиции $$$i$$$ и для каждого подотрезка массива $$$[l, r]$$$, который содержит позицию $$$i$$$ (то есть, $$$1 \le l \le i \le r \le n$$$), Вася вычисляет значение $$$c_{i, l, r}$$$ следующим образом. Вася выписывает на листочек числа из массива с позиции $$$l$$$ до позицию $$$r$$$, всего $$$len=r-l+1$$$ чисел (среди которых обязательно есть $$$a_i$$$), и сортирует выписанные числа по возрастанию. После чего Вася находит, на какой позиции $$$j$$$ в полученном отсортированном массиве стоит число $$$a_i$$$. Если таких позиций несколько, то среди них он выбирает ту, которая максимизирует расстояние от середины массива — позиции $$$mid = \lceil (len+1) / 2 \rceil$$$ ($$$len / 2 + 1$$$ в случае четного $$$len$$$ и $$$(len+1)/2$$$ в случае нечетного $$$len$$$). Полученное расстояние $$$|j - mid|$$$ и есть искомая величина $$$c_{i,l,r}$$$.

Например, если у Васи был массив $$$a=\{5,1,3,2,1,7\}$$$, а $$$i=2$$$, $$$l=2$$$, $$$r=5$$$, то Вася выпишет на листочек числа $$$\{1,3,2,1\}$$$, отсортирует их и получит массив $$$\{1,1,2,3\}$$$, длина которого равна 4. Середина этого массива находится на позиции $$$4/2+1=3$$$, а искомое число $$$a_i=1$$$ стоит в этом массиве на позициях 1 и 2. Среди этих двух позиций Вася выбирает ту, которая дальше от середины, то есть, позицию 1. Искомая разность между позициями равна 2, и это и есть значение $$$c_{2,2,5}$$$.

Для каждой позиции $$$i$$$ Вася вычисляет величину $$$b_i$$$, которая равна максимуму среди значений $$$c_{i,l,r}$$$ среди всех подотрезков, содержащих позицию $$$i$$$.

Как вы видите, определение числа $$$b_i$$$ достаточно сложное. Помогите Васе вычислить значения $$$b_i$$$ для всех позиций массива.

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