Роман Сайонис пишет письмо с угрозами для Харли Квин. Он использует простой текстовый редактор и обычную 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$$$. Дина Лэнс, отвечающая за оружейные запасы, делает выбор по следующим критериям:
- Требуется купить ровно $$$m$$$ единиц оружия.
- Среди $$$m$$$ купленных единиц оружия должно быть не менее $$$k$$$ различных видов.
- Среди всех наборов, удовлетворяющих первым двум критериям, надо выбрать набор с максимальной суммарной мощностью.
- Среди всех таких наборов максимальной мощности требуется выбрать такой, в котором максимальное количество единиц оружия одного вида минимально.
Помогите ей с выбором и найдите такой оптимальный набор. Если наборов с такими свойствами несколько, выведите любой подходящий.
В первой строке даны три целых числа $$$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
On each tickets issued in public transport in Kazaan, $$$6$$$ digits number is printed. To pass the time of the trip, young Aliya often plays a game like this: she tries to place arithmetic operations and brackets between the numbers on the ticket number so that the result is an expression equal to $$$100$$$. At the same time, the numbers between which no operations and brackets were inserted are glued into one number. Aliya has a few rules:
- The numbers in the resulting expression must not contain leading zeros. Moreover, it is not considered that the number $$$0$$$ contains leading zeros, and therefore it is allowed.
- You can use only operations plus, minus, multiply and divide, as well as negation.
- In the process of calculating the value of an expression, division by $$$0$$$ should not occur, and the results of all divisions must be integers.
Formally, the expression that Aliya can get must satisfy the following grammar:
- Expression is (term) or (expression «+» term) or (expression «-» term)
- Term is (factor) or (term «*» factor) or (term «/» factor)
- Factor is (number) or («-»factor) or («(» expression «)»)
- Number is a sequence of digits without leading zeros
Here are examples of some correct expressions, as well as the numbers to which they are equal: 2*(3+4) $$$= 14$$$, 0+0 $$$= 0$$$, -{}-239-{}-179 $$$= (-(-239)) - (-179) = 239 + 179 = 418$$$, (17+13)/6 $$$= 5$$$, 0/10 $$$= 0$$$ (zero can be divided), -(21+12) $$$= -33$$$, (((8))*(9)) $$$= 72$$$.
Here are examples of some incorrect expressions: 2(3+4), 2**2, -239-179-, 17+13/6 (because $$$13$$$ cannot be divided by $$$6$$$), 10/0 (you cannot divide by zero), 0/0 (even so), 1+().
Aliya asks you to help her find such expressions for all possible ticket numbers. She understands that you may not be able to find expressions for all numbers. And for some numbers such expressions do not exist at all. However, the more numbers for which you find the desired expression, the better.
The input consists of several lines. Each line contains $$$6$$$ digits, the ticket number.
For each ticket number print the desired expression, or «No solution», if such an expression does not exist or you could not find it.
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
There is only one test in this task, except for an example. It lists all ticket numbers in ascending order. For each number, you should output the correct expression or the string «No solution». Otherwise, you will receive $$$0$$$ points.
If the output format is correct, your output will be evaluated based on the number of numbers for which you have found the desired expression. Let $$$x$$$ be the number of numbers for which you have found the desired expression, and $$$T$$$ be the number of numbers for which such an expression exists.
The points for your output is $$$\lfloor score (x) \rfloor$$$, where $$$score$$$ is a piecewise linear function, the break points of which are the points $$$(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)$$$.
Formally, $$$score(x)$$$ can be calculated as follows:
| $$$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))$$$ |