1. Поиск в массиве ≡

В первой строке входных данных содержатся натуральные числа n и m.

Во второй строке задаются n элементов первого массива, отсортированные по возрастанию, а в третьей строке – m элементов второго массива.

Элементы обоих массивов - целые числа, каждое из которых по модулю не превосходит 10⁹

Формат входных данных

Первая строка входных данных содержит числа n и m - количество чисел в первом и втором массиве.

В следующей строке идут n чисел a_i.

В третьей строке идут m чисел b_i.

Формат выходных данных

Требуется для каждого из m чисел вывести в отдельную строку "YES", если это число встречается в первом массиве, и "NO" в противном случае.

Ограничения

0 < n,m ≤ 10⁵

 − 10⁹ < a_i, b_i ≤ 10⁹

Примеры тестов

3 3
2 3 5
1 2 3

NO
YES
YES

3 4
1 2 2
1 2 4 5

YES
YES
NO
NO

C31. Свой магический квадрат ≡

У нас есть квадрат 3×3, заполненный числами. А вам нужно вычислить ближайший к нему магический квадрат.

Дистанция между квадратами вычисляется, как сумма модулей разниц между соответствующими клетками квадратов.

Пусть первый квадрат - это F, второй - S, тогда дистанцией будет ∑|F[y][x] − S[y][x]|.

А под магическим квадратом мы понимаем любой квадрат 3 × 3, заполненный 9 различными последовательными числами таким образом, что сумма чисел в каждой строке, каждом столбце и на обеих диагоналях была одинакова

Пример квадратов:

3 5 79 11 1315 17 19 - не является магическим квадратом, так как числа не образуют единую последовательность.

2 9 47 5 36 1 8 - удовлетворяет всем условиям. Числа можно собрать в последовательность: 1,2,...,9

Формат входных данных

На вход программе подаётся три строки, каждая из которых содержит по три числа a_i.

Формат выходных данных

В первой строке вывести разницу между квадратами.

А в следующих трёх - сам получившийся магический квадрат.

Если существует несколько квадратов с одинаковой разницей, то вывести любой.

Ограничения

 − 10⁹ ≤ a_i ≤ 10⁹

Примеры тестов

3 5 7
9 11 13
15 17 19

36
10 15 8
9 11 13
14 7 12

0 0 0
0 0 0
0 0 0

20
-3 2 1
4 0 -4
-1 -2 3

M31. Кошачьи шпионы ≡

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

Мяуканье представляет из себя набор из букв m, e, o, w, причем этих букв может быть много, но одинаковые буквы всегда идут подряд.

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

Настоящие коты никогда не ошибаются и издают правильно мяуканье, а вот собаки-шпионы всегда допускают хотя бы одну ошибку.

Формат входных данных

Первая строка входного файла содержит одно целое число: n - количество допрошенных особей.

В следующих n строках содержится целое число m_i и строка s_i длинны m_i.

Формат выходных данных

Выходной файл должен содержать одно целое число - количество шпионов.

Ограничения

0 < N ≤ 10⁵

0 < m_i ≤ 10⁵

0 < ∑m_i ≤ 4 * 10⁵

Примеры тестов

5
4 meow
11 meeeeooooow
4 miow
4 myau
5 hello

3

7
7 bonjour
7 alaykum
8 dobryden
2 ep
9 reverence
4 iiti
8 konishua

7

M32. Мускулистый Василий ≡

Программист Вася осознал что не может целыми днями сидеть за компьютером, и решил пойти в спортзал. Однако его тренер, когда узнал, что Вася программист, решил сделать ему особенную тренировку. Он сообщает Васе целое число n - количество повторений, а Вася в свою очередь должен рассчитать сколько подходов ему надо сделать.

Выносливость Васи оценивается одним целый числом m и означает сколько повторений он сделает за первый подход. Каждый следующий подход Вася немного устает, и сможет сделать на k повторений меньше, чем в предыдущий подход.

Помогите Васе выяснить, за какое наименьшее количество подходов он выполнит поручение тренера. Если Вася окончательно устанет прежде, чем справится с задачей, выведите -1.

Формат входных данных

Первая строка входного файла содержит 3 числа: n - количество повторений, m - количество повторений в первом подходе, k - снижаемое количество повторений.

Формат выходных данных

Выходной файл должен содержать одно единственное число - минимальное количество подходов или -1, если такое невозможно.

Ограничения

0 < N ≤ 10¹⁸

0 ≤ K ≤ M ≤ 10⁹

Система оценки и описание подзадач

Баллы за подзадачи начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Примеры тестов

10 4 1

4

100 50 20

-1

M33. Космический побег ≡

Инопланетянин по имени "Скр" живет в плоском мире. Скр снова не доел мамин суп, поэтому теперь он в бегах... Летя на своём корабле он увидел перед собой маленькую планету - круг радиуса r. На планете нет ничего, кроме ярких фонарей. Эти фонари настолько яркие, что освещают на сколько угодно большое расстояние, однако сквозь поверхность планеты они просветить не могут. Всего n фонарей, i-ый фонарь представляет из себя тонкий столб высоты h_i, на верхушке которого располагается светящийся элемент, освещающий все в зоне своей видимости. Укажем точку отчета - произвольную точку на поверхности планеты. И для каждого фонаря известно вещественное число a_i - угол в радианах по часовой стрелки от точки отсчета до основания фонаря (см иллюстрацию).

Скр пытается уйти от погони, поэтому хочет спрятаться в тени, то есть в такой точки планеты, которую не освещает ни один фонарь.

Инопланетянин очень не хочет попасться маме, поэтому просит вас о помощи. Он хочет узнать, есть ли на этой планете место, в котором мог бы спрятаться.

Фонари располагаются перпендикулярно поверхности планеты.

Формат входных данных

В первой строке входных данных располагается целое число n - количество фонарей на планете.

Во второй строке одно вещественное число r - радиус планеты.

В следующих n строках располагаются по два вещественных числа - a_i и h_i - угол в радианах от начальной точки до основания фонаря и высота фонаря.

Формат выходных данных

Выведите в единственной строке YES, если существует место, в котором Скр может спрятаться, и NO в ином случае.

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ r ≤ 100

1 ≤ a_i ≤ 2 * π

0 < h_i < 100

Система оценки и описание подзадач

Баллы за подзадачи начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Иллюстрации к примерам

Иллюстрация к примеру 1



Иллюстрация к примеру 2



Иллюстрация к примеру 3

В иллюстрациях начало отсчёта располагается в верхней точке.

Примеры тестов

3
4
1.047197551 1.000000000
3.141592653 2.000000000
5.235987755 0.500000000

YES

3
4
1.047197551 11.000000000
3.141592653 4.000000000
5.235987755 6.000000000

NO

3
4
1.047197551 11.000000000
3.141592653 4.000000000
4.712388980 5.000000000

YES

M34. Секретный секрет ≡

У Артема есть очень важный секрет. А так как Артем ещё и программист, то компьютерам свою тайну он не доверяет и хранит её в сейфе с особым замком.

Недавно Артем проговорился о том, как устроен этот сейф. Чтобы открыть замок сейфа нужен секретный ключ, ключ называется секретным так как состоит из нескольких других ключей.

Вы пришли к Артему в гости и пока он заваривает вам чай решили осмотреть его комнату. Там вы обнаружили ключницу с N ключами. Немного покрутив эти ключи, вы поняли, что каждый из них может трансформироваться в 4 формы.

Именно вам Артем до этого проговорился про устройство своего сейфа. Поэтому вы знаете, что для его открытия нужно объединить K ключей и порядке в котором это нужно сделать.

Попробуйте “чисто теоретически” понять, возможно ли этими ключами открыть сейф. И если это возможно, то как нужно скомбинировать эти ключи.

Формат входных данных

На вход программе в первой строке подаются два целых числа N, K.

Во-второй идут K целых чисел - формы ключей, которые нужно сложить, чтобы открыть сейф.

В следующих N строках перечисляются ключи, каждая строка - 4 целых числа - 4 формы, которые может принять ключ. F₀, ..., F₃

Формат выходных данных

Выходной файл должен содержать последовательность из K различных целых чисел от 1 до N задающих номера ключей для каждого составляющего секретного ключа.

Если решения нет, выходной файл должен содержать единственное число -1.

Ограничения

1 ≤ N, K ≤ 12

0 ≤ F_i ≤ 128

Примеры тестов

5 4
84 69 83 84
65 66 67 68
84 84 84 84
83 84 83 84
67 82 69 84
69 79 82 83

4 5 3 2

9 7
66 97 100 101 114 105 107
72 101 108 108 111
32 116 111 32
97 108 108 32
109 121 32 32
102 97 110 115
32 97 110 100
32 116 111 32
100 117 99 107
102 117 110 115

-1

M35. Урок ИЗО ≡

Петя пришел в на урок изобразительного искусства. Там ему выдали 3 100-миллилитровых банки с красками разных цветов. Цвет краски задается 3 целыми числами r, g и b- ее насыщенностью красного, зеленого и синего соответственно. Учительница задала Пете смешать краски так, чтобы получить 100мл краски цвета r_x, g_x, b_x.

Краски смешиваются следующим образом:

Пусть есть a₁ миллилитров краски цвета r₁, g₁, b₁ и a₂ миллилитров краски цвета r₂, g₂, b₂. Тогда новая краска будет иметь объем a₁ + a₂ мл, а ее красный цвет будет вычисляться по формуле a₁ r₁ + a₂ r₂a₁ + a₂. Зеленый и синий цвета вычисляются аналогично.

Вам надо помочь Пете и сказать сколько миллилитров каждой краски надо взять, чтобы получить нужный цвет. В ответе выведите целую часть объемов красок. Если искомую краску получить невозможно, выведите -1.

Формат входных данных

В первой строчке располагаются 3 целых числа - r₁, g₁, b₁ - цвета первой краски.

Во второй - r₂, g₂, b₂ - цвета второй краски

В третьей - r₃, g₃, b₃ - цвета четвертой краски

В последней строчке располагаются три целых числа r_x, g_x, b_x - цвет результирующей краски.

Формат выходных данных

Выведите 3 целых числа - целые части количества миллилитров первой, второй и третьей красок соответственно. Если искомую краску получить невозможно, выведите -1.

Ограничения

Все числа целые и неотрицательные.

r₁ + g₁ + b₁ = 255

r₂ + g₂ + b₂ = 255

r₃ + g₃ + b₃ = 255

r_x + g_x + b_x = 255

Система оценки и описание подзадач

Баллы за подзадачи начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Примеры тестов

255 0 0
0 255 0
0 0 255
100 55 100

39 21 39

255 0 0
0 255 0
0 0 255
255 0 0

100 0 0

55 100 100
100 55 100
100 100 55
80 80 95

44 44 11

55 100 100
100 55 100
100 100 55
80 60 115

-1

O31. Нервный друг ≡

У вас есть друг Вася, которому надо перед большой публикой произнести речь. Но когда Вася волнуется, он начинает заикаться и чихать. Вам необходимо выяснить какую же речь пытается сказать ваш друг.

Когда Вася заикается, он повторяет букву через дефис. А когда он чихает, он издает звук «atishoo», и слово, которое он начал произносить, становится не разобрать, и вы его игнорируете.

Формат входных данных

На вход программе подаётся одна строка S длины L - речь, которую вы услышали от Васи.

Формат выходных данных

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

Ограничения

0 < L ≤ 10⁵

A < S[i] ≤ z + !′,

Примеры тестов

Hel-l-l-llo w-w-woratishoowo-orl-ld

Hello world

L-La-a-atisho-o-o-ooLol-l-l

Lol

atishatisho-o-ooooh, f-futur-r-re self, please don'tatishooforgi-iv-ve me and do-o no-o-o-o-ot hit me with the baseball bat again-n!

ooh, future self, please forgive me and do not hit me with the baseball bat again!

O32. Мужики и яма ≡

n строителей несут одну балку. И вдруг перед ними оказываются k ям. Строители, не долго думая, двинулись прямиком через эти ямы.

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

Но строители не всемогущи, поэтому если в какой-то момент суммарный вес строителей, находящихся над пропастью, превышает суммарный вес строителей, стоящих на земле, то у остальных не хватает сил выдержать висящих на балке, и те падают в яму.

Благо яма не глубокая, поэтому все отделаются легким испугом.

Когда хотя бы один человек падает, все остальные прекращают движение, и ваше наблюдение заканчивается.

Формат входных данных

Первая строка входного файла содержит два числа: n количество строителей, k количество ям.

Вторая строка список координат относительно начала балки строителей и их веса: p₁, w₁, ..., p_n, w_n. Координаты рабочих считаются от левого конца балка

Третья строка координаты краёв ям: l₁, r₁, ..., l_k, r_k.

Формат выходных данных

Выходной файл должен содержать одно число - количество упавших строителей.

Ограничения

0 < N * K ≤ 10⁶

0 < l_i, r_i ≤ 10⁹

0 < p_i,  < p_i + 1 ≤ 10⁹

1 < ∑w_i ≤ 10⁹

Примеры тестов

3 1
0 1 1 1 2 1
1 1

0

3 1
0 1 1 3 2 1
1 1

1

O33. Роботы ДПС ≡

В дорожной службе Берляндии испытываю новую технологию - роботизированных инспекторов. Пока что доступен лишь один пост. Сотрудники этого поста роботы, поэтому они не могут сами принимать решений, они лишь выполняют приказы.

Каждую машину можно отнести к одному из типов нарушений. (Например «машина, превысившая скорость», «машина с выключенными фарами»)

Также всегда существует тип «машина без нарушений», который означает что машину оштрафовать не за что.

Вы можете давать роботам приказы штрафовать определённый тип машин. Так как роботы ещё не очень продвинутые, они не могут в один момент времени штрафовать сразу за несколько типов нарушений.

Также оказалось что роботы долго устанавливают в свою программу приказы, поэтому после получения указания они пропускают K машин без штрафов вовсе.

За километр до поста установлена скрытая камера, поэтому вы заранее знаете в какой последовательности и какого типа машины проедут через ваш пост.

Ваша задача продемонстрировать властям Берляндии ценность новой технологии, поэтому вам надо оштрафовать как можно больше машин.

Список нарушений, которые могут вам встретиться: speed - Превышение скорости. headlights - Езда с выключенным светом. phone - Использование телефона во время управления авто. walker - Не пропустил пешехода. belt - Не пристёгнут ремень безопасности.

Формат входных данных

Первая строка входного файла содержит два числа: N, K - Количество машин, которые проедут через пост, Количество машин, необходимое для смены режима камеры.

В следующих N строках описываются машины, которые проедут через ваш пост.

Сначала одно число M - количество нарушений у машины, затем перечисляются сами нарушения

Формат выходных данных

Выходной файл должен содержать одно целое число - максимальное количество штрафов, которое сможет сделать робот.

Ограничения

0 < N, K ≤ 10⁶

Примеры тестов

5 1
2 speed headlights
1 speed
1 phone
1 headlights
1 headlights

4

6 1
1 speed
0
1 phone
1 phone
0
1 headlights

4

O34. Саша и кофе ≡

Программист Саша пьет кофе всегда из одной и той же кружки, которую он никогда не моет.

Когда кофе находится в кружке достаточно долго, оно оставляет на ней кофейное кольцо.

Иногда Саша подливает кофе в кружку, от чего уровень кофе поднимается, и все кольца, которые оказываются ниже уровня кофе растворяются.

Саша может выполнить 3 действия:

1. Налить в кружку coffee_i миллилитров кофе.
2. Выпить coffee_i миллилитров кофе.
3. Определить сколько кофейных колец сейчас на кружке.

Считаем, что после каждого действия Саши кофе в кружке стоит достаточно долго, чтобы кольцо успело образоваться.

Формат входных данных

Первая строка входных данных содержит число n - количество действий, которые сделал Саша.

В следующих n строках идет:

• + coffee_i - Саша доливает в кружку coffee_i миллилитров кофе.
• - coffee_i - Саша выливает из кружки coffee_i миллилитров кофе.

Гарантируется, что Саша не пытается выпить больше кофе, чем есть в кружке. Изначально в кружке нет ни миллилитра кофе.

Формат выходных данных

Требуется вывести количество кофейных колец, которое было на кружке после каждого действия Саши. Каждое в новой строке.

Ограничения

0 < n ≤ 10⁷

0 < с_i ≤ 10⁸

Гарантируется, что объем кофе в стакане никогда не достигнет 2³².

Примеры тестов

14
+ 108
+ 105
+ 110
+ 101
- 32
+ 32
+ 32
+ 32
+ 32
- 103
- 114
- 101
- 101
- 100

1
1
1
1
2
1
1
1
1
2
3
4
5
6

9
+ 1
- 1
+ 1
+ 1
+ 2
+ 3
- 4
+ 1
+ 7

1
1
1
1
1
1
2
2
1

O35. Стильная гирлянда ≡

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

Однако полученная гирлянда не соответствует стилю 2024 года, из-за чего дед мороз поручил своим эльфам вырвать из гирлянды наименьшее количество лампочек так, чтобы полученная гирлянда соответствовала стилю 2024 года.

Изначальная гирлянда задается строкой s. Гирлянда является стильной, если она состоит из последовательно соединенных строк k.

Более формально если строка k = k₁, k₂, …, k_n, то стильная гирлянда будет представлять из себя последовательность следующего вида:

k₁₁, k₂₁…k_n1, k₁₂…k_n2, …k_nm. Где k_ij =  = k_i.

Формат входных данных

Первая строка входных данных - s.

Вторая строка - k.

Гарантируется, что обе строки состоят только из латинских букв. (строчных и прописных)

Формат выходных данных

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

Ограничения

0 < length(s) ≤ 10⁷

Примеры тестов

acbacabba
abac

4

abac
acbacabba

0