Октябрьское возвращение. Совместная тренировка
A. Орнамент
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Орнамент имеет квадратную форму и состоит из равных по размеру квадратных пикселей. Каждый пиксель может быть либо красным, либо белым. Считается, что орнамент сбалансированный, если в любом квадрате 2 $$$\times$$$ 2 присутствуют и белые, и красные пиксели, но их количества не равны друг другу. Приведите пример любого сбалансированного орнамента.

Входные данные

Ввод содержит одно целое число $$$n, (2 \leq n \leq 5000)$$$ - ширину и высоту орнамента в пикселях.

Выходные данные

Выведите $$$n$$$ строк из $$$n$$$ символов $$$R$$$ или $$$W$$$, которые показывают цвет пикселей в орнаменте (красный и белый соответственно). Из всего множества возможных ответов выведите любой.

Пример
Входные данные
3
Выходные данные
RRR
WRW
WWW

B. Ночь стримеров
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На известном сайте для просмотра видеороликов "ЙоўТуб" проходит событие под названием "Ночь стримеров". В эту ночь, которая длится $$$n$$$ секунд, каждый уважающий себя канал организует стрим. Вы подписаны на $$$k$$$ каналов, каждый из которых начнёт свой стрим на $$$a_i$$$-ой секунде и закончит его на $$$b_i$$$-ой секунде $$$(i\in[1;k])$$$. Какое максимальное количество стримов вы сможете посмотреть в эту ночь с начала до конца? Если какой-либо стрим заканчивается, то вы можете в эту же секунду переключиться на другой начинающийся стрим.

Входные данные

В первой строке содержится два числа $$$n$$$ и $$$k$$$ $$$(2 \leq n \leq 200 000, 1 \leq k \leq 200 000)$$$. В следующих $$$k$$$ строках содержатся пары чисел $$$a_i, b_i (1 \leq a_i \lt b_i \leq n)$$$.

Выходные данные

Выведите одно число - ответ на задачу.

Примеры
Входные данные
5 3
1 3
2 5
3 4
Выходные данные
2
Входные данные
6 4
2 3
2 3
2 3
2 3
Выходные данные
1

C. Сборники рассказов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы работаете в издательстве. За последнее время к вам поступили $$$n$$$ рассказов от разных авторов. $$$i$$$-й рассказ имеет длину $$$a_i$$$ страниц. В скором будущем вы запланировали издать $$$k$$$ сборников, $$$i$$$-й сборник содержит $$$b_i$$$ страниц. Каждый сборник может содержать в себе любое количество различных имеющихся рассказов. Каждый рассказ может быть напечатан в любом количестве сборников, ровно как и ни в одном из них. Для каждого сборника определите максимальное количество рассказов, которое он может в себе содержать.

Входные данные

Первая строка содержит два числа $$$n$$$ и $$$k$$$, записанных через пробел ($$$1 \leq n,k \leq 200000$$$). Во второй строке через пробел записаны $$$n$$$ чисел $$$a_i$$$ $$$(1 \leq a_i \leq 10^9)$$$. В третьей строке через пробел записаны $$$k$$$ чисел $$$b_i$$$ $$$(1 \leq b_i \leq 10^{18})$$$.

Выходные данные

Выведите через пробел $$$k$$$ чисел - максимальные количества рассказов для каждого сборника.

Пример
Входные данные
4 3
8 2 3 30
5 29 1
Выходные данные
2 3 0 

D. Проверка базы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана строка из символов '(' и ')'. Проверьте, может ли данная последовательность скобок быть получена из некоторого математического выражения удалением всех чисел и знаков действий.

Входные данные

Первая строка ввода содержит одно натуральное число $$$n$$$, $$$1 \leq n \leq 200000$$$. Во второй строке слитно записана последовательность из $$$n$$$ символов '(' и ')'.

Выходные данные

Выведите $$$YES$$$ или $$$NO$$$ - ответ на вопрос задачи.

Примеры
Входные данные
6
(())()
Выходные данные
YES
Входные данные
3
())
Выходные данные
NO
Входные данные
4
)(()
Выходные данные
NO

E. Футбольный турнир
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В спортивной школе тренируется $$$n$$$ команд. $$$i$$$-я команда имеет силу $$$a_i$$$. Через месяц состоится турнир, в ходе которого каждая команда сыграет по матчу с каждой другой командой. Матч завершается победой одной из команд, если она сильнее другой, либо ничьей, если силы команд равны. В конце турнира каждая команда получит определённое количество очков за сыгранные матчи: 3 очка за каждую победу и 1 очко за каждую ничью.

Николай Васильевич может провести тренировку с какой-либо командой, и тогда её сила увеличится на 1. Он заинтересован, чтобы сумма очков всех команд была максимальной. Какое наименьшее количество тренировок для этого нужно провести?

Входные данные

В первой строке содержится число команд $$$n$$$, $$$(2 \leq n \leq 200000)$$$. Во второй строке через пробел записано $$$n$$$ целых чисел $$$a_i$$$, $$$(1 \leq a_i \leq 10^9)$$$.

Выходные данные

Выведите одно число - ответ на задачу.

Пример
Входные данные
3
6 5 6
Выходные данные
1

F. Астрономия
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Известно, что любая звезда не может быть одновременно видна и с южного полюса, и с северного полюса. Пользуясь этим, Пингвин и Медведь решили посчитать все звёзды в космосе. Они одновременно встали на полюсах, и каждый посчитал те звёзды, которые видны ему. Вам известны эти два числа. При помощи этих данных дайте ответ на вопрос: сколько всего звёзд в космосе?

Входные данные

Две строки ввода содержат числа $$$A$$$ и $$$B$$$ $$$(1 \leq A,B \lt 10^{10^5})$$$ - количества звёзд, насчитанных Пингвином и Медведем. Эти числа не содержат ведущих нулей.

Выходные данные

Выведите одно число - ответ на задачу. Это число не должно содержать ведущих нулей.

Пример
Входные данные
705
33
Выходные данные
738

G. Два муравья
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Два муравья живут в точках $$$a_1$$$ и $$$a_2$$$ координатной прямой. Одновременно и с постоянной скоростью они начинают бежать в определённую сторону. Первый муравей знает, что спустя $$$t_1$$$ секунд он окажется в точке $$$p_1$$$. Второй знает, что через $$$t_2$$$ секунд он будет в точке $$$p_2$$$. Определите, встретятся ли муравьи в одной точке когда-либо. Если да, то спустя какое время они встретятся?

Входные данные

Первая строка содержит 3 целых числа $$$a_1$$$, $$$t_1$$$, $$$p_1$$$, $$$(-10^4 \leq a_1 \leq 10^4,$$$ $$$1 \leq t_1 \leq 10^4,$$$ $$$-10^4 \leq p_1 \leq 10^4,$$$ $$$a_1 \neq p_1)$$$. Вторая строка содержит 3 целых числа $$$a_2$$$, $$$t_2$$$, $$$p_2$$$, $$$(-10^4 \leq a_2 \leq 10^4,$$$ $$$1 \leq t_2 \leq 10^4,$$$ $$$-10^4 \leq p_2 \leq 10^4,$$$ $$$a_2 \neq p_2)$$$. Также $$$a_1 \neq a_2$$$.

Выходные данные

Выведите -1, если муравьи никогда не встретятся. Иначе выведите одно число - время до встречи. Оно должно отличаться от правильного ответа не более, чем на $$$10^{-6}$$$.

Пример
Входные данные
-3 2 5
12 1 10
Выходные данные
2.50000000

H. Загадай желание
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Если человек справа от вас и человек слева от вас имеют одинаковые имена, то вы можете загадать желание. Ваша задача - расставить $$$n$$$ Антонов, $$$n$$$ Владов и $$$n$$$ Стасов в ряд, чтобы среди них было ровно $$$k$$$ человек, которые могут загадать желание.

Входные данные

Ввод содержит два числа $$$n$$$ и $$$k$$$, $$$(1 \leq n \leq 20000$$$, $$$0 \leq k \leq 3*n)$$$.

Выходные данные

Если необходимая расстановка невозможна, выведите -1. Иначе выведите строку из $$$3*n$$$ символов. В ней должно быть ровно по $$$n$$$ символов $$$A$$$, $$$B$$$, $$$C$$$, каждый из которых обозначает человека с соответствующим именем. Если подходящих строк несколько, выведите любую.

Примеры
Входные данные
2 1
Выходные данные
CAABCB
Входные данные
6 17
Выходные данные
-1

I. Робин Гуд
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Шервудском лесу обитают разбойники под предводительством Робина Гуда. Они крайне возмущены тем, что доходы других людей распределены неравномерно. Поэтому любой из разбойников может подойти к двум людям и сделать следующие действия:

1) Посчитать, сколько у них денег. Пусть эти количества равняются $$$a_1$$$ и $$$a_2$$$.

2) Выбрать $$$i, j \in \{1;2\}$$$ $$$(i \neq j)$$$, а также простое число $$$p$$$, такое чтобы $$$a_i$$$ делилось на $$$p$$$.

3) Перераспределить деньги так, чтобы у одного человека стало $$$\frac{a_i}{p}$$$ денег, а у другого - $$$a_j*p$$$. Если от такого перераспределения остаются лишние деньги, то разбойник заберёт их себе. Если наоборот, для таких сумм не хватает денег, то разбойник доплатит их из своего кармана.

Сегодня через Шервудский лес будут идти двое людей с количествами денег, равными 1 и $$$n$$$. Они могут повстречать любое неотрицательное количество разбойников. Разбойники же, естественно, планируют действовать сообща, чтобы суммарно отобрать как можно больше денег. На сколько разбойники смогут разбогатеть?

Входные данные

Ввод содержит одно число $$$n$$$, $$$(1 \leq n \leq 10^9)$$$.

Выходные данные

Выведите одно число - сумму, на которую разбойники смогут разбогатеть, если будут действовать оптимальным образом.

Примеры
Входные данные
8
Выходные данные
3
Входные данные
29
Выходные данные
0

J. Найди кота
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кошки - хищники, поэтому они умеют хорошо маскироваться и рассредотачиваться по местности. Всё, что вы видите, можно представить как строку $$$s$$$ из строчных латинских букв. Там наверняка спрятался кот, если можно выбрать три индекса $$$i \lt j \lt k$$$, таких что строка $$$\overline{s_i s_j s_k}$$$ отличается от строки $$$'cat'$$$ не более чем символом в одной позиции.

Например, в строке $$$'cpython'$$$ спрятался кот, так как можно выбрать индексы 1, 2, 4, и тогда полученная строка $$$'cpt'$$$ отличается от строки $$$'cat'$$$ только во втором символе.

Ваша задача - определить, спрятался ли кот в заданной строке, и если да, то найти его.

Входные данные

На вход подается строка $$$s$$$ из строчных латинских букв. Длина строки $$$|s|$$$ такова, что $$$3 \leq |s| \leq 2*10^5$$$.

Выходные данные

Если в данной строке спрятался кот, то выведите любое из возможных мест, где он бы мог спрятаться. А именно выведите через пробел три индекса $$$i, j, k$$$, таких что $$$1 \leq i \lt j \lt k \leq |s|$$$.

Если в данной строке кот не мог спрятаться, то выведите -1.

Примеры
Входные данные
cpython
Выходные данные
1 3 4
Входные данные
codeforces
Выходные данные
-1
Входные данные
thecatishere
Выходные данные
4 5 6