Мальчик Витя хочет понять, сколькими способами он может расплатиться за свою игрушку стоимостью $$$N$$$ рублей, при этом в магазине нет денег для сдачи. Так как у него есть неограниченное число купюр номиналом 50, 100 и 200 рублей, то ему слишком сложно дать ответ на этот вопрос. Помогите ему.
Первая строка входных данных содержит единственное неотрицательное целое число $$$N$$$ $$$(0 \le N \le 10^6)$$$ — стоимость игрушки.
Выведите количество различных способов купить игрушку стоимостью ровно $$$N$$$ рублей купюрами 50, 100, 200 рублей при условии невозможности выдачи сдачи Вите.
50
1
36
0
200
4
Мэр одного города очень любит следить за тенденциями и воспроизводить их в своём городе. До него дошла новость о популярности велодорожек. Теперь он хочет проложить велодорожки в своём городе и сделать это лучше, чем в других городах! Поэтому он решил сделать велодорожки даже на главной площади города.
Главная площадь представляет собой прямоугольник шириной $$$w$$$ и высотой $$$h$$$, замощённый квадратными плитками со стороной 1. Мэр хочет, чтобы было проложено две велодорожки одинаковой ширины: одна горизонтальная и одна вертикальная. К сожалению, ремонт на площади проводился достаточно давно и на некоторых плитках уже появились трещины. Мэр хочет проложить велодорожки так, чтобы после этого на площади остались только целые плитки. При строительстве велодорожек плитки на их месте убираются. Можно только убирать плитки с площади и нельзя менять местами или добавлять новые. Чтобы потратить меньше денег, мэр хочет сделать велодорожки наименьшей возможной ширины, при этом ширина дорожек должна быть целым числом. Определите, какой должна быть ширина велодорожек.
В первой строке входных данных содержатся три целых числа $$$w$$$, $$$h$$$, $$$n$$$ $$$(1 \le w, h \le 10^9, 1 \le n \le min(w × h, 3 \cdot 10^5))$$$ — ширина и высота площади и количество потрескавшихся плиток соответственно.
В следующих n строках содержится по 2 целых числа $$$x_i$$$, $$$y_i$$$ $$$(1 \le x_i \le w, 1 \le y_i \le h)$$$ — координаты потрескавшихся плиток. $$$(x_i, y_i)$$$ $$$\neq$$$ $$$(x_j, y_j)$$$ при $$$i \neq j$$$.
Выведите единственное число $$$c$$$ $$$(1 \le c \le min(w, h))$$$ — наименьшую возможную ширину велодорожек.
Тесты к этой задаче состоят из 5 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Группа | Баллы | Доп. ограничения | Необх. группы | Комментарий | |
| $$$w,h$$$ | $$$n$$$ | ||||
| $$$0$$$ | — | — | — | — | Тесты из условия. |
| $$$1$$$ | 10 | $$$w,h \le 500$$$ | $$$n \le 500$$$ | 0 | |
| $$$2$$$ | 10 | $$$w,h \le 2000$$$ | $$$n \le 2000$$$ | 0, 1 | |
| $$$3$$$ | 10 | $$$w,h \le 2000$$$ | — | 0, 1, 2 | |
| $$$4$$$ | 30 | $$$w,h \le 3 \cdot 10^5$$$ | — | 0-3 | |
| $$$5$$$ | 40 | — | — | 0-4 | |
5 6 5 5 4 2 6 4 1 2 3 1 4
3
4 3 4 1 1 4 3 4 1 1 3
3
Ниже приведены картинки к примерам из условия. Серым отмечены потрескавшиеся плитки. Во втором примере ширина дорожек равна меньшей из сторон прямоугольника.
 |  |
Даниилу на совершеннолетие состоятельные родители подарили $$$n$$$ квартир и его радости не было предела до того момента, пока он не узнал, что со вступлением во взрослую жизнь появляются налоги. В Берляндии (стране, в которой живет Даниил) действует налог на недвижимость зависящий только от площади максимальной квартиры, которой владеет гражданин. Даниил научился уменьшать площадь квартиры, однако за это тоже нужно платить: пусть площадь квартиры, которую он хочет уменьшить равна $$$x$$$, тогда, тогда квартиру можно уменьшить в $$$y$$$ раз, заплатив ровно $$$y$$$ монет, если после этого площадь останется целым числом, причем для каждой квартиры можно повторять такую операцию несколько раз. Всего у Даниила $$$k$$$ монет, помогите ему узнать какую минимальную площадь максимальной квартиры он может получить, заплатив не более $$$k$$$ монет.
Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ $$$(1 \le n \le 10^5, 0 \le k \le 10^9)$$$ — количество квартир и количество монет соответственно.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dotsc, a_n$$$ $$$(1 \le a_i \le 10^6)$$$ — площади квартир.
Выведите одно число — минимальную площадь максимальной квартиры, которую он может получить.
Решения, корректно работающие для $$$n$$$ $$$\le$$$ 3 получат не менее 30 баллов.
3 10 27 15 20
9
Определим близость двух строк следующим образом: выделим у обоих строк наибольший общий префикс (совпадающие буквы в начале строк) и удалим его. Затем выделим наибольший общий суффикс у обеих строк (совпадающие буквы в конце строк) и тоже удалим его. Сумма длин удалённого префикса и суффикса будет равна близости этих строк.
К примеру, близость строк programming и pruning равна пяти: cначала удаляем наибольший общий префикс pr, затем удаляем наибольший общий суффикс ing. Сумма длин этих строк равна $$$2 + 3 = 5$$$. Также близость строк hse и hsehsehse равна трём, поскольку после удаления наибольшего общего префикса hse, длина наибольшего общего суффикса у пустой строки и hsehse равна нулю.
Дан набор из $$$n$$$ строк. Для каждой строки найдите ближайшую к ней из набора, исключая саму эту строку.
Первая строка входных данных содержит одно целое число $$$n$$$ $$$\ge$$$ 2 — число строк.
Каждая из следующих $$$n$$$ строк содержат одну строку из строчных букв латинского алфавита
В единственной строке выходных данных выведите $$$n$$$ чисел, разделённых пробелом — номера ближайших строк для каждой строки. Строки пронумерованы от 1 до $$$n$$$ в том порядке, в котором они перечисляются во входном файле.
Если возможных ответов несколько, выведите любой из них.
Тесты к задаче разделены на четыре группы. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов из предыдущих групп.
Обозначим за k как максимальную длину строки, а $$$S=\sum_{i = 1}^n |s_i|$$$ как суммарную длину всех строк. $$$(n \le 10^6, k \le 10^6, \le S \le 12 \cdot 10^5)$$$
| Группа | Баллы | n | k | S |
| $$$1$$$ | 15 | $$$n \le 2000$$$ | $$$k \le 100$$$ | $$$S \le 2 \cdot 10^5$$$ |
| $$$2$$$ | 25 | $$$n \le 10^6$$$ | $$$k \le 100$$$ | $$$S \le 10^6$$$ |
| $$$3$$$ | 40 | $$$n \le 10^6$$$ | $$$k \le 10^6$$$ | $$$S \le 10^6$$$ |
| $$$4$$$ | 20 | $$$n \le 10^6$$$ | $$$k \le 10^6$$$ | $$$S \le 12 \cdot 10^5$$$ |
6 pruning problem hse algorithm programming hsehsehse
5 5 6 2 1 3
Валеры есть мультимножество неотрицательных целых чисел размера n и q запросов на изменение этого мультимножества. Мультимножество может содержать несколько одинаковых элементов. Запросы бывают трёх типов:
- Прибавить 1 ко всем числам в мультимножестве.
- Добавить число в мультимножество.
- Удалить один экземпляр значения из мультимножества (если таких чисел в мультимножестве нет, ничего делать не нужно).
Валера — большой поклонник битовых операций, в особенности операции побитового исключающего или (xor). Ему очень хочется узнать каким был результат выполнения операции xor для всех элементов мультимножества после каждого изменения.
В программировании Валера не очень силён, поэтому решить эту задачу предстоит вам.
В первой строке вводятся два целых числа $$$n$$$, $$$q$$$ $$$(1 \le n, q \le 200 000)$$$ — размер массива $$$a$$$ и количество запросов.
Во второй строке вводится $$$n$$$ целых чисел $$$a_1, a_2, \dotsc , a_n$$$ $$$(0 \le a_i \le 10^{18})$$$ — изначальное мультимножество чисел Валеры.
В следующих $$$q$$$ строках будет информация о запросах по одному на строке. Каждая из них будет начинаться с числа $$$type_i$$$ $$$(1 \le type_i \le 3)$$$ — типа запроса.
Если это запрос второго, или третьего типа, через пробел после типа будет число $$$value_i$$$ $$$(0 \le value_i \le 10^{18})$$$ — значение, которое нужно добавить в мультимножество, если $$$type_i$$$ = 2 и удалить, если $$$type_i$$$ = 3.
В $$$i$$$-й строке выведите результат выполнения операции xor для всех чисел в мультимножестве Валеры после первых $$$i$$$ изменений.
Тесты к этой задаче состоят из 3 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп.
| Группа | Баллы | Доп. ограничения | Необх. группы | Комментарий | |
| $$$n,q$$$ | $$$a_i$$$ | ||||
| $$$0$$$ | — | — | — | — | Тесты из условия. |
| $$$1$$$ | 22 | $$$n,q \le 100$$$ | — | 0 | |
| $$$2$$$ | 16 | — | $$$a_i \le 100$$$ | — | Нет запросов второго типа |
| $$$3$$$ | 62 | — | — | 0-2 | |
5 5 0 1 3 4 4 1 2 0 1 3 7 3 6
7 7 5 5 3