Айвар учится в восьмом классе. Он всерьез увлекается двумя школьными предметами — геометрией и технологией. Сегодня он решает геометрический этюд. Из проволоки Айвар вырезал три прямолинейных отрезка длиной $$$a$$$, $$$b$$$ и $$$c$$$ сантиметров соответственно. А из этих трех кусочков проволоки Айвар формирует на столе треугольник. Далее он совершает «события». За одно событие Айвар укорачивает каждый кусочек проволоки (т.е. каждую из сторон треугольника) на $$$1$$$ см и вновь пытается сложить из таких укороченных кусочков проволоки треугольник. Спустя какое минимальное количество событий из имеющихся кусочков проволоки уже нельзя будет сложить треугольник?
На вход программе подаются три натуральных числа $$$a$$$, $$$b$$$ и $$$c$$$ $$$(1 \le a, b, c \le 10^9)$$$.
Гарантируется, что из отрезков заданной длины треугольник составить можно.
В качестве результата Ваша программа должна вывести одно целое число: минимальное количество событий, после которых, из имеющихся кусочков проволоки уже нельзя будет сложить треугольник.
Данная задача состоит из $$$10$$$ тестов (кроме теста из условия). Каждый тест оценивается в $$$10$$$ баллов.
10 18 12
4
В примере после первого события длины прямолинейных кусочков проволоки стали такими: $$$9$$$, $$$17$$$, $$$11$$$. После второго — $$$8$$$, $$$16$$$, $$$10$$$. После третьего — $$$7$$$, $$$15$$$, $$$9$$$. После четвертого — $$$6$$$, $$$14$$$, $$$8$$$, а из таких кусочков треугольник не получится составить.
Исполнитель «Корректор» обрабатывает только маленькие буквы латинского алфавита. Исполнитель «Корректор» умеет:
- Подсчитывать количество символов в слове;
- Вставлять буквы в слове в заданное место;
- Заменять одну букву на другую.
Вам задан алгоритм:
- Вычисляется длина исходной цепочки символов. Если она чётна, то в середину цепочки добавляется буква 'a'. Если длина исходной цепочки нечётна, то в начало цепочки добавляется буква 'b'.
- В полученной цепочке символов каждая буква заменяется буквой, следующей за ней в английском алфавите ('a' — на 'b', 'b' — на 'c' и так далее, 'z' — на 'a').
Получившаяся таким образом цепочка является результатом работы алгоритма.
Например, если применить данный алгоритм к цепочке 'cat', то получится цепочка 'cdbu'. Если применить алгоритм к этому результату ещё раз, то получится цепочка 'debcv'.
Вам необходимо для заданной цепочки (назовём ее базовой) ответить на один из $$$2$$$ вопросов:
- Какая цепочка символов получится, если дважды применить этот алгоритм к базовой?
- В результате двухкратной обработки какой исходной цепочки, получилась базовая? (гарантируется, что такая исходная цепочка существует)
Алфавит английского языка: a b c d e f g h i j k l m n o p q r s t u v w x y z
На вход программе в первой строке поступает цепочка символов. Длина цепочки не превышает $$$100$$$ символов. Во второй строке записан цифрой номер вопроса $$$1$$$ или $$$2$$$.
В качестве результата Ваша программа должна вывести ответ на вопрос.
Данная задача состоит из $$$10$$$ тестов (кроме тестов из условия), где каждый оценивается в $$$10$$$ баллов.
Если Ваша программа умеет отвечать только на один тип вопроса, Вы получите за решение $$$50$$$ баллов.
sc 1
cuce
cuce 2
sc
У Камиля на рабочем столе находятся $$$n$$$ листов бумаги, пронумерованных от $$$1$$$ до $$$n$$$. Чтобы было комфортно писать на $$$i$$$-м листе бумаги, надо чтобы на него попадало как минимум $$$a_i$$$ света. Для того, чтобы освещать листы, у Камиля есть $$$q$$$ ламп, $$$j$$$-я лампа освещает листы с номерами от $$$l_j$$$ до $$$r_j$$$. Если на $$$j$$$-ю лампу подать $$$x$$$ электричества, то освещённость каждого листа бумаги с номером $$$i$$$, где $$$l_j \le i \le r_j$$$, увеличится ровно на $$$x$$$.
Камиль не любит просто так тратить электричество, поэтому он просит вас найти такой минимальный $$$x$$$, что если подать на каждую лампу ровно $$$x$$$ электричества, то ему будет комфортно писать на хотя бы $$$k$$$ листах бумаги. Изначально освещенность каждого листа равна нулю.
В первой строке дано два целых числа $$$n$$$ и $$$k$$$ $$$(1 \le k \le n \le 10^5)$$$ — количество листов бумаги на рабочем столе и количество листов бумаги, которые необходимо осветить, соответственно.
Во второй строке дано $$$n$$$ целых чисел $$$a_1,\ a_2,\ a_3,\ \ldots,\ a_n$$$ $$$(0 \le a_i \le 10^9)$$$, где $$$a_i$$$ — необходимый уровень освещенности для $$$i$$$-го листа бумаги.
В третьей строке дано целое число $$$q$$$ $$$(1 \le q \le 10^5)$$$ — количество ламп.
В следующих $$$q$$$ строках описываются сами лампы, в $$$j$$$-й строке дано два целых числа $$$l_j$$$ и $$$r_j$$$ $$$(1 \le l_j \le r_j \le n)$$$ — границы отрезка листов бумаг, которые освещает $$$j$$$-я лампа.
Выведите одно минимальное целое неотрицательное число $$$x$$$, что если подать на каждую лампу по $$$x$$$ электричества, то будет комфортно писать на хотя бы $$$k$$$ листах бумаги. Если такого $$$x$$$ не существует, выведите $$$-1$$$.
Тесты к этой задаче состоят из нескольких групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов всех необходимых групп.
| Группа | Баллы | Дополнительные ограничения | Необходимые группы | Комментарий |
| 0 | 0 | — | — | Тесты из условия |
| 1 | 25 | $$$n \le 100,\ q \le 100,\ a_i \le 100$$$ | — | В этой группе $$$a_i \le 100$$$, то есть необходимый уровень освещенности каждого листа не больше $$$100$$$. |
| 2 | 20 | $$$n \le 1000,\ q \le 1000,\ k = n$$$ | — | |
| 3 | 30 | $$$q = 1$$$ | — | |
| 4 | 25 | — | 0, 1, 2, 3 | Полные ограничения |
6 37 5 9 8 3 622 44 6
5
10 910 8 9 5 3 1 6 7 4 233 51 47 9
-1
В первом примере первая лампа отвечает за листы $$$2,\ 3,\ 4$$$, а вторая — за $$$4,\ 5,\ 6$$$. Если подать $$$x = 5$$$ электричества на каждую лампу, то освещённости листов станут равны $$$0,\ 5,\ 5,\ 10,\ 5,\ 5$$$ соответственно. В этом случае листы $$$2,\ 4,\ 5$$$ получат необходимую освещенность. Можно показать, что при $$$x \lt 5$$$ не получится осветить хотя бы $$$3$$$ листа необходимым образом.
Вам дано одно целое число $$$x$$$. Найдите количество различныx прямоугольных треугольников ненулевой площади с целыми сторонами, что один из катетов равен $$$x$$$. Два треугольника считаются различными, если их нельзя наложить друг на друга при помощи параллельных сдвигов, поворотов и отражений.
В первой строке дано одно целое число $$$t$$$ $$$(1 \le t \le 5)$$$ — количество наборов входных данных.
В каждой из последующих $$$t$$$ строк дано одно целое число $$$x$$$ $$$(1 \le x \le 10^9)$$$ — длина катета.
Выведите $$$t$$$ строк — количество прямоугольных треугольников с катетом $$$x$$$ для каждого набора входных данных.
Тесты к этой задаче состоят из нескольких групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов всех необходимых групп.
| Группа | Баллы | Дополнительные ограничения | Необходимые группы | Комментарий |
| 0 | 0 | — | — | Тесты из условия |
| 1 | 30 | $$$x \le 40$$$ | 0 | Можно доказать, что при $$$x \le 40$$$, длины всех сторон всех подходящих треугольников не превышают $$$1000$$$. |
| 2 | 25 | $$$x \le 1000$$$ | 0, 1 | |
| 3 | 15 | $$$x \le 10^5$$$ | 0, 1, 2 | |
| 4 | 10 | $$$x = 2^k$$$, $$$1 \le k \le 29$$$ | — | |
| 5 | 20 | $$$x \le 10^9$$$ | 0-4 |
2152
4 0
Для $$$x=15$$$ существует ровно $$$4$$$ различных прямоугольных треугольника с целочисленными сторонами: $$$(8, 15, 17)$$$, $$$(15, 20, 25)$$$, $$$(15, 36, 39)$$$ и $$$(15, 112, 113)$$$.
Прямоугольное поле высоты $$$2^N$$$ и ширины $$$2^N-1$$$ разбито на квадратные единичные клеточки. Сначала выделяется прямоугольная область высоты $$$2^N$$$ и ширины $$$2^{N-1}$$$, прилегающая к левому краю поля. Затем для каждой прямоугольной области справа приклеиваются две области вдвое меньшего размера. Процесс продолжается до тех пор, пока размеры областей не станут $$$2 \times 1$$$, и всё поле не будет заполнено.
Далее, клеточки поля красятся в чёрный и жёлтый цвет по следующему принципу. Самая большая область красится в чёрный цвет. Затем для каждой области нижняя из прилегающих слева областей красится в тот же цвет, что и текущая область, а верхняя — в противоположный.
Результат раскраски для $$$N=4$$$ иллюстрирует следующая картинка:
У Вас есть $$$q$$$ запросов, каждый из которых задаёт произвольный прямоугольник внутри поля. Посчитайте для каждого запроса количество чёрных клеток, которые покрывает соответствующий прямоугольник.
В первой строке дано два целых числа $$$N$$$ и $$$q$$$ ($$$1 \le N \le 30$$$, $$$1 \le q \le 10^4$$$).
Далее идут $$$q$$$ строк, в $$$i$$$-й из них дано описание $$$i$$$-го запроса: четыре целых числа $$$r_i$$$, $$$c_i$$$, $$$h_i$$$, $$$w_i$$$, где $$$r_i$$$, и $$$c_i$$$ — номер строки и номер столбца клеточки, в которой находится левый верхний угол прямоугольника, а $$$h_i$$$ и $$$w_i$$$ — высота и ширина прямоугольника соответственно ($$$1 \le r_i, h_i, r_i+h_i-1 \le 2^N$$$, $$$1 \le c_i, w_i, c_i+w_i-1 \le 2^N-1$$$, $$$1 \le i \le q$$$).
Выведите $$$q$$$ строк, в $$$i$$$-й из них должно быть одно целое число — ответ на $$$i$$$-й запрос.
Отметим, что ответы могут получиться очень большими и не поместиться в 32-битную переменную. Пожалуйста используйте 64-битный тип данных.
Тесты к этой задаче состоят из нескольких групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов всех необходимых групп.
| Группа | Баллы | Дополнительные ограничения | Необходимые группы | Комментарий |
| 0 | 0 | — | — | Тесты из условия |
| 1 | 30 | $$$N \le 5, q \le 1000$$$ | 0 | |
| 2 | 20 | $$$N \le 10, q \le 10^4$$$ | 0, 1 | |
| 3 | 20 | $$$N \le 15, q \le 100$$$ | 0, 1 | |
| 4 | 20 | $$$N \le 20, q \le 10^4$$$ | 0-3 | |
| 5 | 10 | $$$N \le 30, q \le 10^4$$$ | 0-4 | Полные ограничения |
3 41 1 8 72 4 6 44 1 2 66 3 1 3
44 14 10 3
Прямоугольники из примера, для которых нужно посчитать количество чёрных клеточек, показаны на следующем рисунке:
