Роман Сайонис пишет письмо с угрозами для Харли Квин. Он использует простой текстовый редактор и обычную QWERTY-клавиатуру.
В тексте Роман использует строчные и заглавные буквы английского алфавита, цифры, символы «,», «.», «!», «?», «$», «(» и «)», а также пробелы. Текстовый редактор Сайониса настолько прост, что позволяет только дописывать в конец текущего сообщения по одному символу, нажимая на соответствующие клавиши на клавиатуре. Даже если Сайонис хочет набрать несколько одинаковых символов подряд, ему придется нажимать на клавишу заново для каждого символа. Помимо клавиш, соответствующих набираемым символам, Роман использует только клавишу shift, когда это необходимо для набора очередного символа. Среди используемых им символов, shift должен быть нажат, чтобы набрать заглавные буквы и символы «!», «?», «$», «(» и «)». Пробел может быть набран как с нажатой клавишей shift, так и без неё. А во время набирания всех остальных символов, клавиша shift должна быть не нажата.
Роман очень спешит, поэтому хочет набрать сообщение, нажав на клавиши минимальное количество раз. Для экономии времени, он может нажать клавишу shift, набрать несколько символов, и только затем отпустить её — это будет считаться одним нажатием клавиши shift. Помогите Роману определить минимальное количество нажатий на клавиши, которое ему придется сделать.
В первой строке дано одно целое число $$$n$$$ — число символов в тексте Романа ($$$1 \le n \le 10\,000$$$).
Во второй строке дана строка длины $$$n$$$, состоящая из строчных и заглавных букв английского алфавита, цифр, символов «,», «.», «!», «?», «$», «(», «)» и пробелов.
Выведите одно число — минимальное количество нажатий на клавиши, которое придется сделать Роману.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 33 | Текст содержит только буквы | полная | |
| 2 | 33 | В тексте нет пробелов | 1 | первая ошибка |
| 3 | 34 | Без дополнительных ограничений | 1, 2 | первая ошибка |
2 Hi
3
8 How r u?
10
32 You owe me $100 (Im looking 4 u)
36
8 Mm? Okay
10
После окончания разборок с украденным бриллиантом, новообразованной команде «Хищных птиц» нужно заняться множеством организационных вопросов. Разумеется, одним из самых важных является покупка оружия, без которого у них вряд ли есть шансы на долгое существование.
В магазине есть $$$n$$$ различных видов оружия, $$$i$$$-й из которых обладает мощностью $$$a_i$$$. Дина Лэнс, отвечающая за оружейные запасы, делает выбор по следующим критериям:
Помогите ей с выбором и найдите такой оптимальный набор. Если наборов с такими свойствами несколько, выведите любой подходящий.
В первой строке даны три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ — количество видов оружия в магазине, необходимое число единиц оружия и минимальное число различных видов в наборе ($$$1 \le k \le n \le 500\,000$$$, $$$k \le m \le 500\,000$$$).
В следующей строке даны $$$n$$$ целых чисел $$$a_i$$$ — мощность оружия $$$i$$$-го вида ($$$0 \le a_i \le 10^9$$$).
Выведите $$$m$$$ целых чисел $$$b_i$$$ — номера видов оружия, которые входят в искомый набор ($$$1 \le b_i \le n$$$). Для каждого вида, его номер должен встречаться столько раз, сколько он входит в набор.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 10 | Все $$$a_i$$$ различны | первая ошибка | |
| 2 | 10 | $$$m = k$$$ | первая ошибка | |
| 3 | 20 | $$$k = 1$$$ | первая ошибка | |
| 4 | 20 | $$$n, m \le 1\,000$$$ | первая ошибка | |
| 5 | 40 | Без дополнительных ограничений | 1, 2, 3, 4 | первая ошибка |
5 3 2 1 2 3 4 5
5 4 5
5 3 3 1 2 3 4 5
5 4 3
Босс одной из самых могущественных мафиозных семей в Готэме решил, что стал слишком стар и пора передавать бразды правления своим сыновьям. А кроме того, он решил поделить между ними свое поместье. Поместье расположено вдоль прямой дороги и имеет длину $$$l$$$ километров, поэтому оно может быть представлено как отрезок длины $$$l$$$. Всего у мафиозного босса есть $$$n$$$ сыновей и у каждого в поместье есть особняк. Особняк $$$i$$$-го сына расположен на расстоянии $$$a_i$$$ километров от начала поместья, представим его как точку на расстоянии $$$a_i$$$ от левого конца отрезка. Причем, никакие два особняка не находятся в одной точке. Босс решил разделить всё поместье на $$$n$$$ непрерывных частей так, чтобы каждому сыну досталась часть, содержащая его особняк. Иными словами, босс решил целиком разделить поместье на $$$n$$$ отрезков так, чтобы существовал способ распределить отрезки между сыновьями, чтобы отрезок каждого сына содержал его особняк. Отрезок содержит особняк, если точка, соответствующая этому особняку, лежит внутри или на границе отрезка.
Чтобы дележ был наиболее честным, босс решил, что длина самой большой части должна быть минимальна. Помогите ему определить эту длину при оптимальном разделении.
В первой строке даны два целых числа $$$n$$$ и $$$l$$$ — количество сыновей у босса мафии и длина поместья ($$$2 \le n \le 100\,000$$$, $$$1 \le l \le 10^9$$$).
В следующей строке даны $$$n$$$ целых чисел $$$a_i$$$ — позиции особняков сыновей ($$$0 \le a_i \le l$$$). Гарантируется, что все $$$a_i$$$ различны.
Выведите одно вещественное число — длину самой большой части при оптимальном разделении. Ваш ответ будет считаться правильным, если его абсолютная или относительная погрешность не превышает $$$10^{-6}$$$.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 15 | $$$n = 2$$$ | первая ошибка | |
| 2 | 10 | $$$n = l + 1$$$ | первая ошибка | |
| 3 | 30 | $$$n \le 5\,000$$$ | 1 | первая ошибка |
| 4 | 45 | Без дополнительных ограничений | 1, 2, 3 | первая ошибка |
3 10 1 3 8
3.500000000000000
3 2 0 1 2
0.666666666666667
Так как Кассандра еще слишком маленькая, чтобы водить машину, она перемещается по Готэму на общественном транспорте. На билетиках, которые выдают в общественном транспорте, пишут $$$6$$$ цифр — его номер. Чтобы скоротать время поездки, Кассандра часто играет в такую игру: она пытается расставить между цифрами из номера билетика арифметические операции и скобки таким образом, чтобы в результате получилось выражение, равное $$$100$$$. При этом, цифры, между которыми не вставили никакие операции и скобки, склеиваются в одно число. У Кассандры есть несколько правил:
Формально, выражение, которое Кассандра может получить, должно удовлетворять следующей грамматике:
Вот примеры некоторых корректных выражений, а также числа, которым они равны: 2*(3+4) $$$= 14$$$, 0+0 $$$= 0$$$, -{}-239-{}-179 $$$= (-(-239)) - (-179) = 239 + 179 = 418$$$, (17+13)/6 $$$= 5$$$, 0/10 $$$= 0$$$ (ноль делить можно), -(21+12) $$$= -33$$$, (((8))*(9)) $$$= 72$$$.
Вот примеры некоторых некорректных выражений: 2(3+4), 2**2, -239-179-, 17+13/6 (потому что $$$13$$$ не делится на $$$6$$$ нацело), 10/0 (на ноль делить нельзя), 0/0 (даже так), 1+().
Касссандра просит вас помочь ей найти такие выражения для всех возможных номеров билетов. Она понимает, что у вас может не получиться найти выражения для всех номеров. А для некоторых номеров таких выражений и вовсе не существует. Однако, чем больше будет номеров, для которых вы найдете искомые выражения, тем лучше.
Входные данные состоят из нескольких строк. В каждой строке даны $$$6$$$ цифр — номер билета.
Для каждого номера билета выведите искомое выражение, либо «No solution», если такого выражения не существует или вы не смогли его найти.
В этой задаче всего один тест, кроме примера. В нем перечислены все номера билетов в порядке возрастания. Для каждого номера вы должны вывести корректное выражение либо строку «No solution». В противном случае, вы получите $$$0$$$ баллов.
Если формат вывода корректен, ваша посылка будет оценена исходя из количества номеров, для которых вы нашли требуемое выражение. Пусть вы нашли выражения для $$$x$$$ номеров. Обозначим за $$$T$$$ количество номеров, для которых такое выражение существует. Баллы за посылку равны $$$\lfloor score(x) \rfloor$$$, $$$score$$$ — кусочно-линейная функция, точками излома которой являются точки $$$(0, 0)$$$, $$$(5, 5)$$$, $$$(55, 10)$$$, $$$(555, 15)$$$, $$$(5555, 20)$$$, $$$(55555, 25)$$$, $$$(T - 55555, 75)$$$, $$$(T - 5555, 80)$$$, $$$(T - 555, 85)$$$, $$$(T - 55, 90)$$$, $$$(T - 5, 95)$$$, $$$(T, 100)$$$.
Формально $$$score(x)$$$ может быть вычислен следующим образом:
| $$$x$$$ | $$$score(x)$$$ | |
| $$$0 \le x | lt; 5$$$ | $$$x$$$ |
| $$$5 \le x | lt; 55$$$ | $$$5 + \frac{x - 5}{10}$$$ |
| $$$55 \le x | lt; 555$$$ | $$$10 + \frac{x - 55}{100}$$$ |
| $$$555 \le x | lt; 5\,555$$$ | $$$15 + \frac{x - 555}{1\,000}$$$ |
| $$$5\,555 \le x | lt; 55\,555$$$ | $$$20 + \frac{x - 5\,555}{10\,000}$$$ |
| $$$55\,555 \le x | lt; T - 55\,555$$$ | $$$25 + 50 \cdot \frac{x - 55\,555}{T - 55\,555 \cdot 2}$$$ |
| $$$T - 55\,555 \le x | lt; T - 5\,555$$$ | $$$75 + \frac{x - (T - 55\,555)}{10\,000}$$$ |
| $$$T - 5\,555 \le x | lt; T - 555$$$ | $$$80 + \frac{x - (T - 5\,555)}{1\,000}$$$ |
| $$$T - 555 \le x | lt; T - 55$$$ | $$$85 + \frac{x - (T - 555)}{100}$$$ |
| $$$T - 55 \le x | lt; T - 5$$$ | $$$90 + \frac{x - (T - 55)}{10}$$$ |
| $$$T - 5 \le x \le T$$$ | $$$95 + (x - (T - 5))$$$ |
123456 987654 111111 000000 001000
1+(2+3+4)*(5+6) 9+87+(6-5)*4 (111-11)/1 No solution 0+0+100+0