Артем пошел на базар покупать фисташки, к сожалению, в некоторых фисташках нет самого ядра. На рынке есть только 1 продавец, торгующий фисташками. Артём знает, что каждый $$$k$$$-й орех не содержит ядра. Например, если $$$k = 3$$$ и Артём взял 7 орехов, то без ядра будет 2 ореха, если он возьмет 9 орехов, то без ядра будет уже 3 ореха.
Артём планировал купить $$$n$$$ орехов, он в математике не силен, поэтому попросил помощи у Вас. Подскажите Артёму, сколько минимум ему надо взять орехов, чтобы там было хотя бы $$$n$$$ орехов с ядрами.
В первой строке вводится целое число $$$n$$$ — количество орехов, которые хочет Артём $$$(1 \le n \le 10^9)$$$.
Во второй строке вводится целое число $$$k$$$ — с какой периодичностью попадаются плохие орехи $$$(2 \le k \le 10^9)$$$.
В единственной строке выведите — сколько минимум надо купить орехов, чтобы среди них были хотя бы $$$n$$$ орехов с ядром.
Тесты в этой задаче разбиты на 4 группы. Баллы за группу начисляются при прохождении всех тестов этой и всех необходимых групп. Примеры из условия не оцениваются.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи |
| 1 | 9 | $$$n \le k$$$ | — |
| 2 | 27 | $$$1 \le n \le 10^5$$$ | — |
| 3 | 22 | $$$k \le 3$$$ | — |
| 4 | 42 | — |
6 2
11
7 3
10
10 5
12
Дана строка $$$s$$$, состоящая из строчных латинских букв. За один ход можно удалить из строки две буквы, если они равны и находятся на одинаковом расстоянии от концов строки. Формально, можно удалить символы $$$s_i$$$ и $$$s_j$$$, если:
- $$$s_i = s_j$$$
- $$$|i - 1| = |n - j|$$$, где $$$n$$$ — длина строки перед удалением
- $$$i \neq j$$$
Необходимо определить минимально возможную длину строки, которую можно получить после последовательности таких операций.
Первая строка содержит строку $$$s$$$ ($$$1 \le |s| \le 10^5$$$), состоящую из строчных латинских букв.
$$$|s|$$$ обозначает длину строки $$$s$$$.
Выведите одно целое число — минимально возможную длину строки после всех возможных удалений.
Тесты в этой задаче разбиты на 5 групп. Баллы за группу начисляются при прохождении всех тестов этой и всех необходимых групп. Примеры из условия не оцениваются.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи |
| 1 | 3 | $$$|s| = 3$$$ | — |
| 2 | 10 | Строка состоит из одинаковых букв | — |
| 3 | 20 | $$$|s| \le 100$$$ | — |
| 4 | 31 | $$$|s| \le 1000$$$ | 3 |
| 5 | 36 | — | 1-4 |
abba
0
abcde
5
aabaa
1
В первом примере можно удалить все символы:
- Удаляем $$$s_1$$$ и $$$s_4$$$ (оба 'a'), остается "bb"
- Удаляем $$$s_1$$$ и $$$s_2$$$ (оба 'b'), строка пуста
Во втором примере нельзя удалить ни одну пару символов.
В третьем примере можно удалить пары 'a' с обоих концов, оставив только центральный символ.
В далёкой волшебной долине растёт древнее Древо Жизни, питаемое волшебными цветами. Каждому цветку нужно ровно $$$t_i$$$ дней, чтобы впитать магическую силу земли и полностью расцвести. Причём $$$i$$$-й цветок начинает расти только после того, как предыдущий закончил расти. Ожидать тяжело, поэтому...
У вас есть $$$M$$$ порций особого ускоряющего удобрения «Быстророст», каждая из которых:
- Мгновенно ускоряет рост одного цветка, и с этого момента он растёт вдвое быстрее (то есть оставшееся до цветения время делится нацело на 2).
- Расходуется полностью после первого использования.
Ваша задача — посчитать, какое минимальное суммарное время ожидания можно достичь, используя удобрения.
Первая строка содержит два целых числа $$$n$$$ и $$$M$$$ ($$$1 \leq n \leq 10^5$$$, $$$0 \leq M \leq 10^9$$$) — количество цветов и число доступных порций удобрения.
Вторая строка содержит $$$n$$$ положительных целых чисел $$$t_1, t_2, ..., t_n$$$ — сколько дней без удобрения требуется каждому цветку, чтобы зацвести. $$$(1 \le t_i \le 10^9)$$$
Одно число — минимальное количество дней, через которое при оптимальном распределении удобрений все цветы закончат расти и предстанут в полном цветении.
Тесты в этой задаче разбиты на 4 группы. Баллы за группу начисляются при прохождении всех тестов этой и всех необходимых групп. Примеры из условия не оцениваются.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи |
| 1 | 10 | $$$M = 0$$$ | — |
| 2 | 13 | $$$M = 1$$$ | 1 |
| 3 | 42 | $$$M \leq 10^5$$$ | 1, 2 |
| 4 | 35 | — | 1-3 |
5 3 8 4 5 3 10
18
1 10 10
0
Миим и Шааш как обычно после уроков решили во что-нибудь поиграть. Идя после школы, они увидели игру Классики, в которую они часто играли в детстве. Но они уже взрослые, поэтому нужна новая игра, и в эту игру должно быть интересно играть вдвоем. Также им очень нравятся палиндромы, поэтому в игре они должны быть обязательно. Миим предложил сделать игру со строкой. Шааш захотел, чтобы игра была активной. В результате они получили шедевр, который назвали Игра 2.
Вначале игры они выкладывают бинарную строку длины $$$n$$$. Затем Миим начинает идти от начала до конца строки, посетив каждый символ один раз. У него есть два варианта действий : либо перейти к следующему символу, либо сказать Шаашу, что он должен стать на произвольном символе строки перед Миимом, после этого они меняются символами. Их цель в конце сделать строку палиндромом.
После нескольких игр они устали и захотели показать в школе, что они придумали. К сожалению, они не записали свои ходы, а без них будет менее интересно. Помогите им понять, как могла проходить игра.
В первой строке входных данных дано целое число $$$n$$$ — длина строки $$$(1 \le n \le 2 \cdot 10^5)$$$.
Во второй строке дана строка длины $$$n$$$ из 0 и 1.
Если способа победить не было, то выведите «NO». В ином случае выведите «YES», если друзья могли выиграть. В следующей строке выведите число $$$m$$$ — количество обменов символов. В следующих $$$m$$$ строках пары чисел $$$l_i \lt r_i$$$ — их позиции на строке во время обмена.
Тесты в этой задаче разбиты на 5 групп. Баллы за группу начисляются при прохождении всех тестов этой и всех необходимых групп. Примеры из условия не оцениваются.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи |
| 1 | 10 | $$$n \le 7$$$ | |
| 2 | 12 | $$$n \le 2\cdot 10^5$$$, размер ответа не более двух | |
| 3 | 29 | $$$n \le 1000$$$ | 1 |
| 4 | 15 | символы строки расположены в порядке неубывания | |
| 5 | 34 | $$$n \le 2 \cdot 10^5$$$ | 1–4 |
3001
YES 1 2 3
801010101
YES 2 1 2 3 4
Артём купил себе приставку и решил играть в неё непрерывно в течение $$$x$$$ часов. Сутки в игровом мире состоят из $$$T$$$ часов. Известно расписание изменения стоимости электроэнергии: в моменты времени $$$t_i$$$ ($$$0 \le t_i \lt T$$$) цена за час меняется на $$$c_i$$$.
Необходимо определить минимальную стоимость, которую придётся заплатить Артёму за $$$x$$$ часов игровой сессии, если он может начать в любой момент времени.
Первая строка содержит два целых числа $$$T, x$$$ — продолжительность суток в часах, продолжительность игровой сессии в часах. $$$(1 \le T, X \le 10^9)$$$.
Во второй строке вводится целое число $$$n$$$ — количество моментов изменения цены $$$(1 \le n \le 10^5)$$$.
В третьей строке вводятся $$$n$$$ целых чисел $$$t_i$$$ — моменты изменения цены ($$$0 \le t_i \lt T$$$).
В четвёртой строке вводятся $$$n$$$ целых чисел $$$c_i$$$ — новая стоимость электроэнергии начиная с момента $$$t_i$$$ ($$$1 \le c_i \le 10^9$$$).
Гарантируется, что $$$t_0 = 0$$$, все моменты $$$t_i$$$ различны, а также $$$t_i$$$ отсортированы в порядке возрастания.
Выведите одно целое число — минимальную стоимость электроэнергии за $$$x$$$ часов игровой сессии.
Тесты в этой задаче разбиты на 6 групп. Баллы за группу начисляются при прохождении всех тестов этой и всех необходимых групп. Примеры из условия не оцениваются.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи |
| 1 | 9 | $$$T, x \le 100$$$ | — |
| 2 | 5 | $$$x$$$ делится нацело на $$$T$$$ | — |
| 3 | 15 | $$$T, X \le 1000$$$ | 1 |
| 4 | 24 | $$$X \le 10^5$$$ | — |
| 5 | 22 | $$$n \le 1000$$$ | — |
| 6 | 25 | — | 1-5 |
24 530 8 165 3 7
15
100 1020 5010 20
100
12 10040 3 6 92 1 5 3
269
В скором времени начнется великая битва между Тун тун тун тун Сахуром и Тралалело Тралала, поэтому Тун тун тун тун Сахур решил собрать войско.
Его войско можно представить как массив из $$$n$$$ натуральных чисел. Тун тун тун тун Сахур не был бы Тун тун тун туном Сахуром, если бы его не заинтересовало $$$q$$$ отрезков этого массива. Для каждого из этих отрезков ему стало интересно: а правда ли, что можно перемешать элементы на этом отрезке так, чтобы каждый следующий элемент делился на предыдущий?
Помогите Тун тун тун тун Сахуру и ответьте на все его запросы.
В первой строке вводятся натуральные числа $$$n$$$, $$$q$$$ — длина массива и число запросов ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq q \leq 2 \cdot 10^5$$$).
Во второй строке вводятся $$$n$$$ натуральных чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).
Затем идут $$$q$$$ строк, в $$$i$$$-й из которых два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$) — границы $$$i$$$-го отрезка запроса.
Для каждого запроса в порядке входа выведите на отдельной строке слово «YES», если элементы на отрезке $$$[l_i, r_i]$$$ можно переставить так, чтобы каждый следующий делился на предыдущий, или «NO» в противном случае.
Тесты в этой задаче разбиты на 5 групп. Баллы за группу начисляются при прохождении всех тестов этой и всех необходимых групп. Примеры из условия не оцениваются.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи |
| 1 | 17 | $$$n, q \leq 100$$$ | — |
| 2 | 21 | $$$n \leq 1000$$$ | 1 |
| 3 | 14 | Массив $$$a$$$ содержит не более 2 различных элементов | — |
| 4 | 36 | $$$n, q \leq 10^4$$$ | 1 |
| 5 | 12 | — | 1-4 |
5 3 1 6 3 9 8 2 4 3 5 3 4
NO NO YES
Команда пиратов уже целый год вместе, и за это время они успели заработать много денег и много штрафов. По итогу года было решено разделить награбленное между командой. По старым пиратским обычаям нельзя просто так разделить поровну, этот вопрос касается и чести пирата. Для решения этого вопроса они открыли древний кодекс, который описывал, как делить в таком случае.
Нулевое правило кодекса гласило: «Награда и штрафы неделимы». Иными словами, итоговая сумма с $$$i$$$-го дела может достаться только одному пирату. При этом нельзя, чтобы сумма не досталась никому.
Первое правило кодекса гласило : «Каждый пират не может уйти в долгах или с ничем». То есть каждый пират суммарно получит положительную сумму монет.
Второе правило кодекса гласило: «Раздел должен быть непрерывным, как путь корабля». То есть дела нельзя разрывать или переставлять – каждый пират получает свою долю только из последовательных дел, как они шли в хронике года.
Третье правило кодекса гласило: «Младшим надо уступать». Это означало, что в начале самый младший выберет первые $$$s_1$$$ дел, затем второй по старшинству выберет следующие $$$s_2$$$ дел и так далее.
Четвертое правило кодекса гласило: «Старших надо уважать». Это означало, что если старший пират получил свою долю, то младший не может получить больше, иначе это будет ударом по репутации. Таким образом, заработанные суммы должны идти в порядке неубывания.
Пятое правило кодекса гласило: «Подумай о ближнем». Для пиратов это правило значило, что как можно больше пиратов должно уйти с деньгами, и они все преследовали эту цель.
Теперь им осталось понять, какое максимальное количество пиратов заработали в этом году. Помогите им с этой задачей.
В первой строке входных данных дано число $$$n$$$ — суммарное количество кладов и штрафов $$$(1 \le n \le 10^5)$$$.
Во второй строке дан массив целых чисел $$$a_1, a_2, \ldots, a_n$$$, где значение $$$a_i$$$ означает, что получили пираты с $$$i$$$-го дела. Если $$$a_i \ge 0$$$, то они заработали $$$a_i$$$ монет, иначе они получили штраф $$$-a_i$$$ монет.
Гарантируется, что $$$a_1 + a_2 + \ldots + a_n \gt 0$$$ и $$$|a_1| + |a_2| + \ldots + |a_n| \le 10^5$$$.
Выведите, какому максимальному количеству пиратов можно выдать награду.
Тесты в этой задаче разбиты на 5 групп. Баллы за группу начисляются при прохождении всех тестов этой и всех необходимых групп. Примеры из условия не оцениваются.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи | |
| 1 | 14 | $$$n \le 15$$$ | ||
| 2 | 20 | $$$n \le 10^3$$$ | 1 | |
| 3 | 18 | $$$0 | lt; a_1 \le a_2 \ldots \le a_n$$$ | |
| 4 | 19 | $$$|a_1| + |a_2| + \ldots + |a_n| \le 100$$$ | ||
| 5 | 29 | $$$n \le 10^5$$$ | 1–4 |
31 2 3
3
57 -5 3 -1 4
3
Во втором примере пираты могут получить (7 - 5), (3 - 1), 4