По кругу на одинаковом расстоянии друг от друга расположены $$$12$$$ точек. Они подписаны числами $$$1,\,2,\,3,\,1,\,2,\,3,\,1,\,2,\,3,\,1,\,2,\,3$$$ (см. рисунок).
Сколько существует остроугольных треугольников с вершинами в этих точках, у которых все три вершины подписаны тремя различными числами? Треугольник называется остроугольным, если все его углы строго меньше $$$90$$$ градусов.
В оригинальном соревновании данная задача подразумевала ввод ответа напрямую в специальное окно ввода.
В данном соревновании решением задачи является программа на любом языке программирования, ничего не считывающая из входных данных и выводящая единственное число — ответ на задачу.
Например, если вы считаете, что ответом на задачу является число $$$-1$$$, то вы можете отправить следующее решение, выбрав в качестве компилятора Python или PyPy:
print(-1)
Шахматная доска $$$n \times n$$$ заполнена целыми числами от $$$1$$$ до $$$n^2$$$. Каждое число встречается ровно 1 раз. Белые клетки пронумерованы подряд, затем начинается нумерация чёрных клеток (см. пример). Левый верхний угол доски всегда является белым.
Пример для $$$n = 4$$$:
Пример для $$$n = 5$$$:
Требуется для матрицы $$$15 \times 15$$$ найти сумму чисел в $$$7$$$ строке. Нумерация строк начинается с $$$1$$$.
Например, на доске размером $$$4 \times 4$$$ (пример 1) сумма чисел в строке с номером $$$3$$$ равна $$$5 + 13 + 6 + 14 = 38$$$.
В оригинальном соревновании данная задача подразумевала ввод ответа напрямую в специальное окно ввода.
В данном соревновании решением задачи является программа на любом языке программирования, ничего не считывающая из входных данных и выводящая единственное число — ответ на задачу.
Например, если вы считаете, что ответом на задачу является число $$$-1$$$, то вы можете отправить следующее решение, выбрав в качестве компилятора Python или PyPy:
print(-1)
У жирного тролля Севы есть два волшебных стула. Если волшебный стул перевернуть, то он превратится в 4 волшебных стула. Однажды Сева решил позвать к себе в гости $$$n - 1$$$ друзей — жирных троллей. Теперь Сева задумался о том, что всех гостей надо будет рассадить на стулья (и самому тоже куда-то сесть). Известно следующее:
Сева слишком занят подготовкой развлекательных мероприятий для друзей, поэтому он просит у вас помощи. Напишите программу, которая определит, можно ли рассадить Севу и его гостей на стулья так, чтобы никто не оказался недовольным.
В первой строке записано одно целое число $$$t$$$ $$$(1 \le t \le 10^4)$$$ — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.
Каждый набор входных данных состоит из одной строки, содержащей одно целое число $$$n$$$ ($$$2 \le n \le 10^9$$$) — общее число троллей ($$$n - 1$$$ гостей и 1 Сева).
Для каждого набора входных данных в отдельной строке выведите «YES» (без кавычек), если можно рассадить всех троллей по стульям так, что ни один из троллей не останется недовольным. И «NO» (без кавычек) в противном случае.
4 2 3 5 7
YES NO YES YES
В первом примере можно посадить двух троллей на 2 стула, не совершая никаких дополнительных переворотов.
Во втором примере не получится сделать рассадку, какое бы количество переворотов не было совершено.
В третьем примере можно перевернуть один волшебный стул. Всего получится 5 волшебных стульев, после чего каждого из 5 троллей можно посадить на 1 волшебный стул.
В четвёртом примере можно сделать 4 переворота волшебных стульев. Всего получится 14 волшебных стульев — каждому из 7 троллей достанется по 2 стула.
Недавно Софья Ковалевская прочла про понятие «идеальной пары» целых чисел. Пара целых чисел $$$a$$$ и $$$b$$$ называется идеальной, если $$$\gcd(a, b) = \min(a, b)$$$, где $$$\gcd$$$ — наибольший общий делитель двух целых чисел.
Теперь Софья не может уснуть, пока не узнает количество чисел из полуинтервала $$$[l, r)$$$, образующих идеальную пару с числом $$$n$$$. Помогите ей обрести покой на ближайшую ночь.
В первой строке записано одно целое число $$$t$$$ $$$(1 \le t \le 10^4)$$$ — количество ночей, в которые Софья не может уснуть. Далее следуют $$$t$$$ наборов входных данных.
Каждый набор входных данных состоит из одной строки, содержащей три целых числа $$$n$$$, $$$l$$$, $$$r$$$ $$$(1 \le n \le l \lt r \le 10^{18})$$$ — число, для которого необходимо найти количество идеальных пар, и границы полуинтервала соответственно.
Для каждого набора входных данных в отдельной строке выведите искомое число — количество чисел, образующих с $$$n$$$ идеальную пару в данном полуинтервале $$$[l, r)$$$.
4 1 2 3 5 5 15 2 2 3 1 1 1000000000000000000
1 2 1 999999999999999999
В первом примере $$$\gcd(1, 2) = \min(1, 2) = 1$$$. Других чисел в полуинтервале нет, поэтому ответ равен $$$1$$$.
Во втором примере $$$\gcd(5, 5) = \min(5, 5) = 5$$$, $$$\gcd(5, 10) = \min(5, 10) = 5$$$. Несмотря на то, что число $$$15$$$ подходит числу $$$5$$$, оно не входит в полуинтервал $$$[5,15)$$$ и, следовательно, в ответе не учитывается.
Буквально несколько секунд назад произошла хакерская атака на Цитадель Риков. Несколько одинаковых копий опасной программы проникло на главный сервер. Никто не знает, откуда взялся этот злосчастный вирус и какие у него цели (не иначе опять Рик C137 балуется).
Пока известно только одно: каждая копия вируса, не останавливаясь, порождает несколько таких же копий каждую секунду. Каждая созданная копия начинает делать то же самое - порождать несколько своих копий. А те копии начинают порождать свои копии...
На борьбу с вирусом брошены все свободные Рики и Морти, но пока даже неизвестны параметры роста вируса. Всё, что удалось выяснить — что спустя $$$3$$$ секунды после атаки на сервере было уже $$$1029$$$ копий вируса, а через $$$6$$$ секунд — $$$352947$$$.
Помогите Совету Риков - вычислите точное число копий вируса, находившихся на сервере через $$$t$$$ секунд после начала атаки.
В первой строке записано одно целое число $$$q$$$ $$$(1 \le q \le 11)$$$ — количество наборов входных данных. Далее следуют $$$q$$$ наборов входных данных.
В каждой $$$i$$$-й строке, соответствующей $$$i$$$-му набору входных данных, дано единственное целое число $$$t_i\text{ }\left(0 \le t_i \le 10\right)$$$ — количество секунд, прошедших с момента проникновения вредоносного вируса в Цитадель Риков.
Для каждого набора входных данных выведите одно целое число — количество одинаковых копий вируса спустя $$$t_i$$$ секунд с момента начала хакерской атаки.
2 3 6
1029 352947
Тест соответствует данным из условия (так как только эти данные есть в нашем распоряжении).
В первом тестовом примере спустя $$$t_1 = 3$$$ секунды с момента атаки на сервере находилось $$$1029$$$ одинаковых копий опасного вируса.
Во втором тестовом примере спустя $$$t_2 = 6$$$ секунд с момента атаки их уже стало $$$352947$$$.
Паровозик Томас устроился поездом в московское метро. Он будет работать на кольцевой линии. За свою рабочую смену он должен проехать свой маршрут ровно $$$k$$$ раз подряд.
Маршрут начинается и заканчивается на станции Октябрьская. Весь маршрут поезд проезжает за $$$d$$$ минут. Как только поезд заканчивает маршрут, он тут же отправляется на новый. Соответственно, если поезд начал маршрут во время $$$t$$$, то на следующий маршрут он отправится ровно во время $$$t + d$$$, не раньше и не позже.
Томас нашел статистику загруженности поездов: если поезд начал маршрут в момент времени $$$i$$$, то в поезд зайдет $$$a_i$$$ пассажиров на всем маршруте. Всего за день будет выполнено $$$n$$$ маршрутов - в $$$1$$$-ю, $$$2$$$-ю, $$$\dots$$$, $$$n$$$-ю минуты.
Томасу стало интересно, в какой момент времени начинается самая загруженная смена. Загруженность смены равна суммарному количеству зашедших в поезд пассажиров по всем $$$k$$$ маршрутам, которые Томас проедет.
Гарантируется, что всегда существует хотя бы одна смена, за которую можно проехать маршрут $$$k$$$ раз подряд.
В первой строке записано одно целое число $$$t$$$ $$$(1 \le t \le 10^4)$$$ — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.
Каждый из наборов входных данных задаётся следующим образом.
В первой строке следуют три целых числа $$$n, k, d$$$ $$$(1 \le n, k, d \le 2 \cdot 10^5)$$$ — общее количество отправляющихся на маршрут поездов за день, количество маршрутов в трудовых обязанностях Томаса и продолжительность одного маршрута.
Во второй строке следует $$$n$$$ целых чисел $$$a_i$$$ $$$(1 \le a_i \le 10^9)$$$ — количество пассажиров, зашедших в поезд на маршруте, начавшемся в момент времени $$$i$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Гарантируется, что всегда существует хотя бы одна смена, за которую можно проехать маршрут $$$k$$$ раз.
Для каждого набора входных данных выведите одно целое число — максимальное количество пассажиров, которых можно перевести за одну смену.
2 10 3 2 2 3 4 9 8 7 6 1 5 10 10 3 3 1 1 1000000000 1 1 1000000000 1 1 1000000000 1
19 3000000000
В первом наборе входных данных существуют следующие возможные смены из $$$k = 3$$$ маршрутов с продолжительностью $$$d = 2$$$:
Максимальное количество перевезенных пассажиров достигается на сменах, начатых во $$$2$$$-й и $$$5$$$-й моменты времени.
Во втором наборе входных данных существуют только $$$4$$$ возможные смены из $$$k = 3$$$ маршрутов с продолжительностью $$$d = 3$$$:
Максимальное количество людей будет перевезено за смену $$$3$$$ и только за неё.
Алиса Селезнёва из 2074 года и Зелибоба с улицы Сезам решили сыграть во внеземную игру с внеземными правилами.
Игровое поле представляет собой таблицу из $$$n \times m$$$ клеток размером $$$1 \times 1$$$.
В левом верхнем углу $$$\left(1,1\right)$$$ таблицы расположена фишка. Будем говорить, что фишка передвинулась на $$$k$$$ клеток, если из клетки $$$\left(x,y\right)$$$ она перешла в клетку $$$\left(x+k,y\right)$$$ или $$$\left(x,y+k\right)$$$.
Фишка двигается по следующим правилам:
Алиса и Зелибоба управляют фишкой по очереди. Алиса начинает игру. Если игрок в свой ход не может передвинуть фишку, то он проиграл. Для таблицы размером $$$n \times m$$$ определите победителя при условии, что оба игрока используют оптимальную стратегию.
В первой строке записано одно целое число $$$t$$$ $$$(1 \le t \le 5 \cdot 10^4)$$$ — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.
Каждый набор входных данных состоит из одной строки. Строка содержит два целых числа $$$n, m$$$ $$$(1 \le n, m \le 3 \cdot 10^4; n \cdot m \le 3 \cdot 10^4)$$$ — размеры таблицы соответственно.
Для каждого набора входных данных выведите «Alice», если Алиса выиграет игру, или «Bob», если выиграет Зелибоба, при условии использования обоими игроками оптимальной стратегии.
6 2 2 3 3 4 4 3 4 4 3 3 9
Bob Alice Bob Alice Alice Alice
В первом тестовом примере Алиса не может сделать первый ход, так как из клетки $$$\left(1,1\right)$$$ она обязана ходить либо в $$$\left(1,3\right)$$$, либо в $$$\left(3,1\right)$$$, что не представляется возможным из-за того, что размеры доски равны $$$2 \times 2$$$.
Во втором тестовом примере Алиса может сделать первый ход, например, в $$$\left(1,3\right)$$$, переместив фишку на две клетки, после чего Говорун не может передвинуть фишку на $$$3$$$ клетки.
В третьем тестовом примере, если Алиса передвинет фишку в клетку $$$\left(1,3\right)$$$ или $$$\left(3,1\right)$$$, то Зелибоба, передвигая фишку в клетки $$$\left(4,3\right)$$$ и $$$\left(3,4\right)$$$ соответственно, добивается победы, так как Алиса не сможет сделать следующий ход.
Бендер «Сгибальщик» Родригез насмотрелся аниме, после чего решил приобщиться к японской культуре поплотнее. Для начала Бендер выбрал наиболее близкий ему род искусства — «Оригами»: ведь тут всего лишь надо сгибать бумагу то туда, то сюда, он справится в два счёта.
Но, проведя дни за сгибанием и разгибанием листов бумаги, Бендер осознал всю глубину философии, лежащей за таким простым процессом. Теперь Бендер готов поделиться этим сакральным знанием с вами, не упустите свой шанс!(*)
Например, представьте перед собой прямоугольный лист бумаги... Представили? Мысленно согните его пополам справа-налево ровно посередине, затем пополам снизу-вверх, и, наконец, пополам слева-направо... Согнули? Кажется, что перед Вами все тот же прямоугольный лист бумаги, но он больше никогда не станет прежним... Развернув согнутый в несколько раз лист, Вы немедленно увидите следующую картину:
$$$\text{ }$$$
Полученную Вами следующей последовательностью сгибов:
$$$\text{ }$$$
$$$\text{ }$$$
$$$\text{ }$$$
Вы два раза согнули лист бумаги по вертикальной линии сгиба и один раз по горизонтальной линии сгиба, поэтому, получилась таблица из $$$6$$$ вертикальных сгибов и $$$4$$$ горизонтальных сгибов, направленных либо к Вам, обозначенных $$$U$$$ (от слова $$$\text{up}$$$), либо от Вас, обозначенных $$$D$$$ (от слова $$$\text{down}$$$).
Если Вы сделаете $$$m$$$ сгибов по вертикали и $$$n$$$ по горизонтали, то получится $$$2^n$$$ строк, в каждой из которых будет по $$$2^m-1$$$ вертикальных сгибов, и $$$2^m$$$ столбцов, в каждом из которых будет по $$$2^n-1$$$ горизонтальных сгибов.
Пронумеруем строки целыми числами от $$$1$$$ до $$$2^n$$$ сверху-вниз, а столбцы – целыми числами от $$$1$$$ до $$$2^m$$$ слева-направо. Вертикальные сгибы в каждой строке пронумеруем целыми числами от $$$1$$$ до $$$2^m-1$$$, а горизонтальные сгибы в каждой строке – целыми числами от $$$1$$$ до $$$2^n-1$$$. Сможете ли Вы для заданных сгибов сообщить, в какую сторону они направлены?
В первой строке даны два целых числа $$$n$$$ и $$$m$$$ $$$\left(0 \le n \le 29, 0 \le m \le 29\right)$$$ — суммарное количество операций сгиба вдоль горизонтальных и вертикальных линий, соответственно.
В следующих $$$n+m$$$ строках заданы сами операции сгиба прямоугольного листа в хронологическом порядке:
Затем дано целое число $$$q$$$ $$$\left(1 \le q \le 10^4\right)$$$ — количество запросов.
В следующих $$$q$$$ строках приведены сами запросы по одному в каждой строке:
Ответьте на все запросы в том порядке, в котором они даны. Выведите ответы в виде одной строки из $$$q$$$ символов, каждый из которых либо $$$U$$$, либо $$$D$$$.
1 2 RL DU LR 10 v 1 1 v 1 2 v 1 3 v 2 1 v 2 2 v 2 3 h 1 1 h 2 1 h 3 1 h 4 1
DDUUDDDDUU
2 2 LR UD DU RL 24 v 1 1 v 1 2 v 1 3 v 2 1 v 2 2 v 2 3 v 3 1 v 3 2 v 3 3 v 4 1 v 4 2 v 4 3 h 1 1 h 1 2 h 1 3 h 2 1 h 2 2 h 2 3 h 3 1 h 3 2 h 3 3 h 4 1 h 4 2 h 4 3
UDDDDUUDDDDUDUUDUUUDDUDD
$$$\textbf{Важная информация по языку Python}$$$: команда языка input() при чтении строк возвращает строку вместе с символом перевода строки на конце. Советуем использовать комбинацию input().strip() для чтения строк в данной задаче.
Пояснения к примерам:
Первый тестовый пример полностью соответствует рисунку из условия.
Второй тестовый пример:
(*) - услуга осознания тарифицируется посекундно, стоимость зависит от порядка сгибов и количества запросов, а так же взаимного расположения галактик «Млечный Путь» и «Туманность Андромеды».