Секретный объект $$$X$$$-$$$0619$$$ расположен на прямоугольной территории размерами $$$H \times W$$$ метров.
Для установки видеонаблюдения за территорией объекта было решено использовать особых дронов. Каждый из этих дронов может быть настроен на наблюдение за квадратной областью произвольного размера и расположения. Каждая точка на территории объекта должна быть в зоне наблюдения хотя бы одного дрона. Ввиду того, что рядом с секретным объектом $$$X$$$-$$$0619$$$ могут быть расположены другие секретные объекты, то каждая точка вне территории объекта не должна попадать в поле наблюдения ни одного из дронов.
Определите какое минимальное количество дронов для этого потребуется?
В единственной строке через пробел задается два целых числа $$$H$$$ и $$$W$$$ $$$(1 \leqslant H, W \leqslant 1000)$$$ — длина и ширина секретного объекта.
Выведите одно целое число — минимальное количество дронов, которое потребуется чтобы установить наблюдение за объектом $$$X$$$-$$$0619$$$.
3 9
3
4 3
2
Жюри очень любят четные числа. Сейчас у нас есть одно число из $$$n$$$ цифр, но оно может оказаться нечетным. Это нужно срочно исправлять! Для этого вам предлагается совершить следующую операцию ровно один раз:
Например, используя данную операцию из числа $$$5317$$$ можно получить числа $$$5137, 3517$$$ и $$$1357$$$. Порадуйте членов жюри и сделайте число четным!
В первой строке задано одно целое число $$$n$$$ $$$(1 \le n \le 10^3)$$$ — количество цифр в числе $$$n$$$.
Во второй строке задано одно целое число, состоящее из $$$n$$$ цифр. Это число не содержит нулей.
Если вы не сможете обрадовать жюри, выведите «NO».
Иначе в первой строке выведите «YES». Во второй строке выведите два целых числа $$$L,R$$$ $$$(1 \le L \le R \le n)$$$ — границы подотрезка, на котором вы выполнили операцию. В третьей строке выведите полученное после операции число.
Если существует несколько возможных ответов, то выведите любой из них.
5 43153
NO
6 654321
YES 1 6 123456
Быстросчет Алгебрович захотел придумать метод генерации чисел, для этого он создал алгоритм, который принимает одно целое положительное число $$$x$$$ и генерирует результат по следующей схеме:
- Привести текущее число $$$x$$$ к числу $$$x-1$$$
- Привести текущее число $$$x$$$ к числу $$$2 \cdot x$$$
Все шаги алгоритма должны чередоваться, то есть алгоритм должен работать в следующем порядке: $$$1,2,1,2,\dots$$$. Также алгоритм может начать работу не с первого, а со второго шага и должен выполнять шаги в таком порядке: $$$2,1,2,1,\dots$$$. Например, из числа $$$7$$$ можно сгенерировать числа: $$$7 \rightarrow 14 \rightarrow 13 \rightarrow 26 \rightarrow \dots$$$ или числа $$$7 \rightarrow 6 \rightarrow 12 \rightarrow 11 \rightarrow \dots$$$.
Теперь Быстросчету для числа $$$i$$$ захотелось узнать, а какие числа могут сгенерировать число $$$i$$$, если из них запустить алгоритм? Более точно, определим множество $$$B_i$$$ как все числа, вызвав алгоритм из которых может быть получено число $$$i$$$ после какого-то (возможно, нулевого) количества итераций алгоритма, а за $$$|B_i|$$$ обозначим количество чисел в множестве $$$B_i$$$. Числа из множества $$$B_i$$$ будем называть генерирующими для числа $$$i$$$. Быстросчету интересно узнать суммарное количество генерирующих чисел для всех целых чисел от $$$l$$$ до $$$r$$$, иными словами значение $$$\sum\limits_{i = l}^{r} |B_i|$$$, помогите ему посчитать ответ!
В единственной строке задано два целых числа $$$l,r$$$ $$$(1 \le l \le r \le 10^{18})$$$.
Выведите одно целое число — ответ на задачу.
9 14
34
Наступает важный экзамен, который будут писать $$$n$$$ школьников. Все школьники будут рассажены в один кабинет, в котором находятся $$$n$$$ рабочих мест. Каждый школьник и рабочее место пронумерованы от $$$1$$$ до $$$n$$$. Всего школьники сдают $$$m$$$ экзаменов. Вам поручено подготовить план рассадки сдающих на каждый экзамен, удовлетворив следующие условия:
- В любой день все школьники должны сидеть на разных местах, то есть для каждого школьника должно быть предоставлено ровно одно место.
- Каждый раз школьники должны сидеть по-разному, то есть не должно быть двух таких дней, в которые бы планы рассадки полностью совпали.
- В соседние экзамены никакой школьник не должен сидеть на одном и том же месте.
План на один экзамен задается $$$n$$$ целыми числами $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le n)$$$ и означает: $$$1$$$-й школьник должен сесть на место $$$a_1$$$, $$$2$$$-й школьник должен сесть на место $$$a_2$$$, ..., $$$n$$$-й школьник должен сесть на место $$$a_n$$$.
В единственной строке задано два целых числа $$$n,m$$$ $$$(1 \le n,m \le 10^3)$$$.
Если удовлетворить требования не получится, то в первой строке выведите «IMPOSSIBLE». Иначе выведите «POSSIBLE», а в следующих $$$m$$$ строках выведите по $$$n$$$ целых чисел в каждой — рассадка на очередной экзамен.
6 3
POSSIBLE 1 2 3 4 5 6 6 5 4 3 2 1 1 3 2 5 6 4
4 30
IMPOSSIBLE
Постройте на плоскости выпуклый шестиугольник с площадью $$$S$$$, все координаты которого являются целыми числами.
В единственной строке задано одно целое число $$$S$$$ $$$(3 \le S \le 10^9)$$$.
Выведите двенадцать целых чисел $$$x_1,y_1,x_2,y_2,\ldots,x_6,y_6$$$ $$$(-10^9 \le x_i, y_i \le 10^9)$$$ — координаты вершин шестиугольника. Выводите вершины в порядке обхода фигуры по или против часовой стрелки. Все точки должны быть различными.
22
3 7 5 8 8 5 6 2 3 3 2 5
Двенадцатого июня будет праздноваться день города Ижевска! В связи с праздником в ИжГТУ решили вывесить большую надпись «Izhevsk». Чтобы сделать ее красивее и интереснее, решили заказать несколько плакатов, нарисованных в разном стиле. На каждом из них написан текст так, что после их объединения в каком-то порядке они образуют надпись «Izhevsk».
Сегодня Хрисипп забрал сделанные плакаты из магазина, их оказалось ровно три. Помогите ему соединить их в один большой плакат.
В единственной строке задано три непустые строки из букв латинского алфавита, разделенные одним пробелом. Длина каждой строки не превосходит $$$5$$$.
В одной строке выведите три слова — правильное расположение плакатов. Разделяйте их пробелами.
I zh evsk
I zh evsk
he Iz vsk
Iz he vsk
Рассмотрим последовательность целых чисел $$$a_1, a_2, \ldots, a_n$$$. Определим функцию $$$g(x,y)$$$ следующим образом:
Вам дается $$$q$$$ пар целых чисел $$$l_1, r_1, \ldots, l_q, r_q$$$. Посчитайте $$$q$$$ значений $$$g(l_1,r_1), g(l_2,r_2), \ldots, g(l_q, r_q)$$$.
В первой строке задано два целых числа $$$n,q$$$ $$$(1 \le n, q \le 3 \cdot 10^5)$$$.
Во второй строке задано $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ $$$(-100 \le a_i \le 100)$$$.
Далее следует $$$q$$$ строк. В каждой строке задано два целых числа $$$l_i, r_i$$$ $$$(1 \le l_i \le r_i \le n)$$$.
Выведите $$$q$$$ строк, в каждой из которых выведите одно целое число — ответ на очередном отрезке. Выводите ответы для отрезков $$$l,r$$$ в том же порядке, в котором они заданы во входных данных.
4 2 4 1 3 5 2 3 3 4
13 23
На одной из олимпиад по программированию организаторами был проведен опрос. Тема опроса — знание языков программирования. Каждому респонденту было предложено $$$n$$$ вариантов ответа на выбор, можно было выбирать сколь угодно вариантов. Последний вариант ответа «другое», таким образом респондент показывает, что он знает какие-то языки, которых в вариантах ответа нет.
Были составлены итоги опроса, а именно $$$n$$$ чисел $$$a_1,a_2,\ldots,a_n$$$. Ровно $$$a_1$$$ респондентов выбрали первый вариант, ровно $$$a_2$$$ респондентов выбрали второй вариант и так далее. К сожалению, в итогах не значится количество людей, которые были опрошены — их количество не фиксировалось, однако теперь оказалось нужно его знать, хотя бы примерное. Вас попросили по имеющимся данным определить, сколько минимум и максимум программистов могли опросить, чтобы получить такой итог. Можно заявлять, что каждый человек выбрал хотя бы один вариант ответа (как минимум — он бы выбрал вариант «другое»).
В первой строке задано одно целое число $$$n$$$ $$$(1 \le n \le 5000)$$$.
Во второй строке задано $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ $$$(0 \le a_i \le 10^9)$$$.
Выведите два целых числа — минимум и максимум, соответственно.
3 1 0 1
1 2
Афанасий недавно придумал великую теорему, великую теорему Афанасия! Так вот, великая теорема Афанасия (сокращенно — ВТА) утверждает, что любое число можно представить в виде произведения двух неотрицательных чисел без нулей на конце.
Афанасий попросил вас проверить, верна ли его теорема для числа $$$n$$$.
Вам нужно решить задачу независимо для $$$t$$$ различных наборов входных данных.
В первой строке задано одно целое число $$$t$$$ $$$(1 \leqslant t \leqslant 10^5)$$$ — количество тестов.
В каждой из следующих $$$t$$$ строк задано по одну целому числу $$$n$$$ $$$(1 \leqslant n \leqslant 10^{18})$$$ — значение числа $$$n$$$ для каждого из тестов.
Для каждого из набора входных данных выведите два целых числа $$$a, b$$$ $$$(1 \leqslant a, b \leqslant n)$$$, удовлетворяющих ВТА для числа $$$n$$$.
Если существует несколько подходящих ответов — выведите любой из них.
2 55 40
11 5 5 8
Данил, известный космический путешественник, решил сыграть с вами в игру «Караван». Он выписал последовательность $$$1,2,3,\ldots,n$$$ (именно в таком порядке) и затем выбрал какой-то подотрезок — два целых числа $$$l,r$$$ $$$(1 \le l \le r \le n)$$$ и перемножил все числа с индексами от $$$l$$$ до $$$r$$$ включительно на целое положительное число $$$x$$$. После чего все числа были случайным образом перемешаны.
Ваша задача разгадать, каким образом Данил изменил перестановку.
В первой строке задается одно целое число $$$n$$$ $$$(1 \leqslant n \leqslant 2 \cdot 10^5)$$$ — длина перестановки.
Во второй строке задается $$$N$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ $$$(1 \leqslant a_i \leqslant 10^{18})$$$ — перемноженные числа.
Выведите три целых числа $$$l, r, x$$$ $$$(1 \leqslant l \leqslant r \leqslant n; 2 \leqslant x)$$$ — левая граница диапазона, правая граница диапазона и коэффициент увеличения соответственно.
Гарантируется, что ответ существует. Если существует несколько ответов, то выведите любой из них.
8 6 8 8 6 1 10 7 2
3 5 2
5 3 5 111111111111111 222222222222222 4
1 2 111111111111111
В первом примере последовательность $$$1,2,3,4,5,6,7,8$$$ была превращена в $$$1,2,6,8,10,6,7,8$$$ и после перемешивания стала равна $$$6,8,8,6,1,10,7,2$$$.
На новую гонку на дронах уже приглашено $$$n$$$ участников. По задумке организаторов как только начнется гонка, дрон каждого участника начнет двигаться со своей стартовой позиции на свою финишную позицию по прямой траектории. Организаторы уже определили для каждого участника стартовую позицию.
Изначально планировалось также выбрать отдельную финишную позицию для каждого участника отдельно. Однако теперь ради зрелищного финала организаторы гонки хотят перенести финишные позиции всех участников в одну точку. Разумеется дистанция между стартовой и финишной позицией для всех участников должна быть равна. Изменить стартовые позиции участников уже нельзя, но можно изменить дистанцию гонки.
Помогите организаторам найти такую дистанцию и общую финишную позицию или сообщите что их не существует.
В первой строке задано одно целое число $$$n$$$ $$$(1 \le n \le 10^5)$$$ — количество участников гонки.
Далее следует $$$n$$$ строк, в каждой из которых задано два целых числа $$$x_i, y_i$$$ $$$(-1000 \le x_i, y_i \le 1000)$$$ — стартовая позиция $$$i$$$-го участника гонки. Участники могут стартовать из одинаковых точек.
Если не существует финишной позиции, подходящей для всех участников, то выведите «NO».
Иначе выведите «YES». Затем, во второй строке выведите три числа $$$x_e, y_e, d$$$ — координаты финишной позиции и расстояние от старта до финиша.
Если существует несколько вариантов ответа, то выведите любой из них.
Ваш ответ будет признан правильным, если дистанция гонки для всех участников будет равна с точностью до $$$10^{-6}$$$.
2 2 -1 4 -3
YES 2.000000 -3.000000 2.000000