Задача AA. Amazon ≡

Условие

Сказочные шахматы — раздел шахматной композиции. В произведениях этого раздела присутствуют изменения некоторых из общепринятых правил игры или применяются необычные фигуры или доски.

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

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

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

Первая строка входных данных содержит два натуральных числа, записанных через пробел: x₁ и y₁ — координаты белой амазонки. Во второй строке в том же формате содержатся координаты чёрного короля x₂ и y₂. Гарантируется, что позиции фигур различны.

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

Выведите Yes или No — ответ на вопрос задачи.

Ограничения

1 ≤ x₁, x₂, y₁, y₂ ≤ 8

Пояснение к примерам

Смотри рисунок. Во втором примере король может атаковать амазонку.

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

7 6
7 8

Yes

6 7
7 8

No

Задача AB. Bonus points ≡

Условие

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

На доске записаны два n-значных числа, первое — состоящее только из цифры d₁, второе — только из цифры d₂. Определите, какая цифра находится на k-м месте в сумме этих чисел. Места пронумерованы слева направо начиная с 1.

Вам же нужны дополнительные баллы?

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

Четыре строки входных данных содержит четыре натуральных числа: n, d₁, d₂ и k. Гарантируется корректность k.

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

Выведите одну десятичную цифру — ответ на вопрос задачи.

Ограничения

1 ≤ n ≤ 10⁹

1 ≤ k ≤ n + 1

1 ≤ d₁, d₂ ≤ 9

Пояснение к примеру

В примере n = 2 (складываются двузначные числа), d₁ = 5 (первое число 55), d₂ = 8 (второе число 88). Сумма 55 + 88 = 143. k = 1 (учителя интересует первая цифра результата). На первом месте в числе 143 цифра 1.

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

2
5
8
1

1

Задача AC. Clustering of triangles ≡

Условие

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

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

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

Входные данные содержат натуральное число N, за которым следует 9 × N целых чисел, задающих координаты вершин:

(X1i, Y1i, Z1i), (X2i, Y2i, Z2i), (X3i, Y3i, Z3i), где i = 0, 1, …, (N − 1).

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

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

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

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

Ограничения

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

 − 1000 ≤ (Xki, Yki, Zki) ≤ 1000,

2 ≤ N ≤ 10⁵.

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

6

 166  -61 -108
-175  122  133
 -81   96   71

-100 -228  246
 -64   58  -68
 -85   12  -27

 131 -140 -101
  37 -114  -39
  72  -35  -46

 137 -186 -113
  84 -127  -70
  66   11  -34

-140 -143  121
 -45  -73   98
  34   31   25

-135 -170 -173
 -86   45 -252
  39  124   31

3

3 3 2 0
2 4 1
1 5

Задача AD. Digital circuit ≡

Условие

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

Логические элементы представлены как прямоугольные области, обрамленные рамкой из символов '#' (ASCII 35).

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

Описание может быть разбито на части, разделенные пробелами либо разнесенные по разным строкам.

Провода обозначены в виде последовательностей из символов '.' (ASCII 46).

Оставшееся свободное пространство схемы заполнено пробелами.

Рамки никаких двух элементов не могут стыковаться между собой (между ними всегда имеется зазор).

Провода могут стыковаться между собой только под углом в 90^∘.

Параллельные провода не могут идти вплотную друг к другу (между ними всегда имеется зазор).

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

Провод не может пройти через занятую элементом область.

Шина это набор связанных между собой проводов.

На заданном изображении требуется выделить набор логических элементов и связанных с ними шин.

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

Входные данные содержат ASCII-изображение.

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

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

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

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

В начале каждого набора указывается число его элементов,
затем следуют их номера
(начиная с нуля).

Ограничения

Общее количество символов изображения не превосходит 10⁶.

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

           #####        
#######    #abc#        
# xyz #    #123#        
#     #....#####   #####
#######    .       #   #
           .    ...#abc#
............    .  #   #
.               .  #####
. ############  .       
. #  123     #  .       
. #    xyz   #........  
. ############       .  
.         .          .  
...........          .  
          .    #########
          .....#  abc  #
 #######  .    #########
 #xyz  #...             
 #     #  .       ##### 
 # abc #  ........#123# 
 #######   .      ##### 
           #####        
           #xyz#        
           #####        

8
abc 123
xyz
abc
123 xyz
abc
xyz abc
123
xyz

3
6 0 3 4 5 6 7
3 2 3 4
2 0 1

Задача AE. Equidistant strings ≡

Условие

Рассмотрим множество всех возможных строк длиной ровно n символов, состоящих из цифр и строчных букв латинского алфавита.

Расстояние Хэмминга H(A, B) равно количеству позиций i от 1 до n таких что A[i] ≠ B[i].
Определим P(A, B) как множество строк длины n, равноудаленных от A и B ({ C: H(A, C) = H(B, C)}).

Требуется определить количество строк в множестве P(A, B).

Так как ответ может оказаться слишком большим, выведите остаток от его деления на 10⁹.

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

Входные данные содержат две строки: A и B.

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

Выведите единственное целое число — ответ.

Ограничения

1 ≤ n ≤ 10⁴.

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

abc
1b3

41688

ab
ab

1296

Задача AF. Fencing the bishop ≡

Условие

Данная задача является интерактивной. Ваша программа будет взаимодействовать с программой жюри путем отправки и приема сообщений определенного вида.

Шахматная доска представляет из себя поле из 8 на 8 чередующихся белых и черных клеток. Столбцы шахматной доски обозначаются буквами от A до H, строки — цифрами от 1 до 8. Координаты клетки записываются как [столбец][строка], например, E2. Левый нижний угол, клетка A1, имеет черный цвет.

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

Ваша программа должна делать запросы вида "? A B", где A и B — координаты двух клеток игрового поля, левого нижнего и правого верхнего углов прямоугольника, за которым вы хотите установить мониторинг. После каждого запроса слон совершает ход, и вам сообщается в какие из наблюдаемых прямоугольников попал слон после этого хода.

Требуется определить текущее положение слона, сделав не более 6 запросов. Гарантируется, что перемещение слона определено заранее и не зависит от запросов.

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

В первой строке входных данных записана строка color, равная white или black — цвет клетки, на которой изначально стоит слон.

Протокол взаимодействия

Чтобы сделать запрос, ваша программа должна вывести "? A B", где A, B — строки из двух символов, координаты левого нижнего и правого верхнего углов прямоугольника, за которым нужно установить наблюдение.

После установки наблюдения слон совершает ход, и программа жюри отвечает вашей программе строкой S из символов 1 или 0 — где i-й символ равен 1, если слон попал в i-й наблюдаемый прямоугольник.

Когда ваша программа определила текущее положение слона X, она должна вывести "! X", где X — строка из двух символов, координаты клетки слона. После вывода ответа программа должна завершиться.

Если ваша программа сделает недопустимый запрос, то она получит вердикт "Presentation error". Если ваша программа превысит допустимое количество запросов, то она получит вердикт "Wrong answer".

Каждый запрос и вывод окончательного результата должен быть одиночной строкой заканчивающейся одиночным переводом строки (\n). Буфер вывода необходимо сбрасывать после каждой строки:

Ограничения

"A1"  ≤ A, B, X ≤  "H8"

A ≤ B

Пояснение к примерам

Перемещения слона и установленные области наблюдения из первого примера представлены на картинке.

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

white

0

01

000

0000

00000

100100

? B2 E4

? A4 C7

? A7 B8

? E4 F8

? H4 H8

? G1 H2

! E4

black

0

01

? A1 A1

? C3 C3

! C3

Задача AG. Graph minimization ≡

Условие

Пусть нам известны два непересекающихся набора узлов некоторого ориентированного графа: A и B.
Для каждого узла из множества A задан набор всех достижимых из него узлов из B.
При этом узлы из A не должны иметь входящих ребер, а узлы из B — выходящих.

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

Требуется получить граф с минимальным числом ребер, который удовлетворяет заданному описанию.
Если существует несколько вариантов, предпочтение отдается графу с минимальным числом узлов.

В качестве ответа следует вывести число узлов и ребер в полученном графе.

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

Входные данные содержат целые числа: N — размер множества A и M — размер множества B.
Далее следуют наборы узлов множества B, достижимых из каждого узла множества A.

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

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

Выходные данные должны содержать два целых числа: число узлов и ребер.

Ограничения

1 ≤ (N, M) ≤ 1000

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

5 4

4 0 1 2 3
4 1 0 3 2
4 3 1 0 2
4 0 3 2 1
4 3 2 1 0

10 9

5 4

2 1 0
2 0 2
2 2 3
2 3 0
2 0 1

9 10

Задача AH. Health and light ≡

Условие

В городке N — радостное событие! На единственной улице установят фонарь и откроют аптеку. Помогите градоначальнику установить оптимальное место для размещения этих объектов.

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

У фонаря есть параметр "яркость", выражающий, на каком максимальном расстоянии от фонаря всё еще светло. Например, при яркости, равной 10, фонарь, установленный в точке x = 25, будет освещать улицу на отрезке от 15 до 35, включая границы.

У аптеки есть параметр "удаленность", выражающий, на каком расстоянии домов от нее, люди, живущие в этих домах, будут её посещать. Например, при удаленности, равной 100, аптека, размещенная в точке x = 25, будет посещаться людьми, живущими в домах с координатами на отрезке от 0 до 125, включая границы (домов с отрицательными координатами нет).

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

Первая строка входных данных содержит три натуральных числа, записанных через пробел: n — количество домов, a — яркость и b — удаленность. В следующих n строках через пробел расположены по два неотрицательных целых числа x_i, q_i — координату дома и количество проживающих в нем людей (дома могут быть пустые).

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

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

Ограничения

1 ≤ n, a, b ≤ 10⁵

0 ≤ x_i, q_i ≤ 10⁹

Пояснение к примеру

В примере дано пять домов, яркость фонаря 15 и удаленность аптеки 20. Фонарь может быть установлен либо в точке 15, либо в точке 25, в обоих случаях освещено будет 4 дома. Аптеку можно расположить в точке 20, в этом случае посещать её смогут все жители города.

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

5 15 20
0 6
10 5
20 0
30 7
40 10

4 28

Задача AI. Identical digits ≡

Условие

Женя Славин — первый человек, родившийся на Марсе. Он еще маленький, и очень любит смотреть на электронные часы, висящие напротив его кровати. Больше всего ему нравятся моменты, когда все цифры на табло становились одинаковыми. В такие моменты он всегда радуется и хлопает в ладоши.

Поскольку период обращения Марса вокруг своей оси отличается от земного, марсианские колонисты определили, что:

• в одних марсианских сутках будет ровно h марсианских часов;
• в одном марсианском часе будет ровно m марсианских минут;
• в одной марсианской минуте будет ровно s марсианских секунд.

Текущее время на Марсе — h_M часов, m_M минут и s_M секунд. Через сколько секунд Женя захлопает в ладоши? Время на марсианских электронных часах выводится с ведущими нулями во всех разрядах, лишние разряды не используются.

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

Во входных данных содержатся шесть целых чисел, по одному в строке: h, m и s — описание разбиения марсианских суток, затем h_M, m_M и s_M — текущее время.

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

Выведите одно целое число — количество секунд до того момента, как все цифры на табло станут одинаковыми.

Ограничения

0 ≤ h_M < h ≤ 10⁶

0 ≤ m_M < m ≤ 10⁶

0 ≤ s_M < s ≤ 10⁶

Пояснения к примерам

В первом примере марсианские сутки ничем не отличаются от земных (24 часа по 60 минут по 60 секунд). Сейчас 23 часа 50 минут ровно (на табло горят цифры 23:50:00). Через 10 минут (или 600 секунд) на табло во всех разрядах будут гореть одни нули.

Во втором примере марсианские сутки содержат 627 часов по 5 минут по 777 секунд. Сейчас 49 часов 3 минуты и 2 секунды (на табло горят цифры 049:3:002). Через 61 час 3 минуты и 109 секунд (или 239425 марсианских секунд) на табло во всех разрядах будут гореть одни единицы.

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

24
60
60
23
50
0

600

627
5
777
49
3
2

239425

Задача AJ. Jolly evening ≡

Условие

Марина Цветаева, Андрей Белый и Саша Чёрный коротают вечер за шахматной доской. В каждой партии играют двое, третий ждет своей очереди, чтобы занять место проигравшего. Победитель предыдущей партии в следующей играет белыми фигурами.

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

Андрей Белый любит играть белыми фигурами, Саша Чёрный — черными, Марина Цветаева любит играть любым цветом. Определите количество партий, в которых оба противника играли своим любимым цветом. В самой первой партии встречались Белый (играл белыми) и Черный. Ни одна партия не завершилась вничью.

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

Две строки входных данных содержат два натуральных числа n и k.

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

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

1 ≤ n ≤ 10⁹

1 ≤ k ≤ 100

Пояснение к примеру

Было сыграно 4 партии, игравший белыми выигрывал 1 партию, следующую — проигрывал.

В первой партии Белый — Чёрный оба играют любимым цветом. Игравший белыми Андрей побеждает.

Во второй партии Белый — Цветаева оба играют любимым цветом. Игравший белыми Андрей проигрывает.

В третьей партии Цветаева — Черный оба играют любимым цветом. Игравшая белыми Марина побеждает.

В последней партии Цветаева — Белый только Марина играет любимым цветом. Итого ответ: 3 партии.

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

4
1

3

Задача AK. Karousel ≡

Условие

В детском парке открылся новый аттракцион "Карусель" на n мест. Согласно технике безопасности при её эксплуатации рассаживать детей можно только таким образом, чтобы центр тяжести всех катающихся совпадал с центром карусели и расстояния между ними по окружности были одинаковыми. Например, при n = 6 одновременно могут кататься 2, 3 или 6 ребят, а при n = 5 — только ровно 5. Другими словами, разрешается запустить карусель, если на ней размещено k детей, причём k — делитель n и k ≠ 1.

В очереди к карусели стоит d детей. Дети, которые покатались на карусели, уходят в поисках новых развлечений. Какое минимальное количество запусков аттракциона следует осуществить, чтобы все дети прокатились на карусели ровно по одному разу?

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

Две строки входных данных содержат натуральные числа n и d.

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

Выведите одно натуральное число — ответ к задаче. Если всех ребят прокатить не получится, выведите -1.

Ограничения

1 ≤ (d, n) ≤ 10⁵

Пояснение к примеру

В первом примере дано n = 16 и d = 14 (карусель на 16 мест, в очереди 14 детей). Достаточно 3 запуска карусели: в первый раз прокатятся 8 ребят, во второй — 4, в третий — 2.

Во втором примере дано n = 15 и d = 7. Всех детей прокатить не получится, так как согласно правилам разрешено катать только по 3, 5 или 15 ребят.

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

16
14

3

15
7

-1

Задача B0. Олины торты ≡

Условие

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

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

Входные данные содержат числа M и N, каждое на новой строке.

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

Необходимо вывести единственное число — максимальное количество сахара.

Ограничения

1 < N, M < 10000

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

10
2

5

6
4

1.5

Задача B1. Заплыв ≡

Условие

Оксана любит плавать и готовится к заплыву через Амурский залив. Для подготовки она каждый день приходит в бассейн и проводит там несколько часов, переплывая от одного края бассейна до другого. Длина бассейна, где занимается Оксана — N метров. Она успевает пересечь его за M секунд, и ещё K секунд тратит на разворот. Сколько метров Оксана успеет проплыть за L минут?

Формат входного файла

Первая строка входного файла содержит четыре натуральных числа: N M K L.

Формат выходного файла

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

Ограничения

1 ≤ N, M, K, L ≤ 1000

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

25 76 2 45

865

50 50 1 60

3530

Задача B2. Строки в книге ≡

Условие

В книге на одной странице помещается K строк. Таким образом, на 1-й странице печатаются строки с 1-й по K-ю, на второй - с (K + 1)-й по (2 × K)-ю и т.д. Напишите программу, которая по номеру строки в тексте определяет номер страницы, на которой будет напечатана эта строка, и порядковый номер этой строки на странице.

Формат входного файла

Формат выходного файла

Ограничения

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

50 1

1 1

20 25

2 5

15 43

3 13

Задача B3. Слон на шахматной доске ≡

Условие

Слон — шахматная фигура, которая может двигаться на любое число клеток по диагонали.

Имеется шахматная доска N на N клеток. В клетке с координатами (X; Y) находится слон. Требуется вывести шахматную доску с изображением слона и всех клеток, в которые он может походить.

Клетки чёрного цвета обозначаются символом '#' (ASCII 35), клетки белого цвета обозначаются символом '.' (точка, ASCII 46), клетка со слоном обозначается символом 'X' (ASCII 88), клетка, в которую может походить слон обозначается символом '*' (ASCII 42).

Ось ординат (OY) направлена вертикально вниз. Верхний левый угол доски имеет чёрный цвет и координаты (1; 1).

Формат входного файла

Входной файл содержит целые числа N X Y.

Формат выходного файла

Выходной файл должен содержать N строчек из N символов каждая — изображение шахматной доски.

Ограничения

2 ≤ N ≤ 100

1 ≤ X, Y ≤ N

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

8
3 5

#.#.#.*.
.#.#.*.#
*.#.*.#.
.*.*.#.#
#.X.#.#.
.*.*.#.#
*.#.*.#.
.#.#.*.#

3 1 2

#*#
X#.
#*#

Задача B4. K-й бит в числе ≡

Условие

Дано целое неотрицательное число x, требуется вернуть значение k-го бита числа x, то есть k-й разряд двоичного представления числа x. Разряды нумеруются с 0 начиная с младшего. Считается что число содержит неограниченное количество лидирующих нулей.

Формат входного файла

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

Формат выходного файла

Входной файл должен содержать одно число  — значение k-го бита числа x.

Ограничения

0 ≤ x ≤ 2 ⋅ 10⁹

0 ≤ k ≤ 300

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

0 10

0

123 0

1

12345 100

0

Задача B5. Стремление к нулю ≡

Условие

Дано число N и массив из S целых чисел A_i.

За одну операцию можно заменять число N на любое из чисел N + A_i, N − A_i, N × A_i, N / A_i.

Второй операнд может быть любым элементом массива A.

Деление выполняется нацело, с округлением вниз.

Необходимо рассчитать минимальное количество операций, необходимых, чтобы получить из числа N число 0.

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

Первая строка входных данных содержит целое число N.

Вторая — целое число S.

Третья — S целых чисел, массив A.

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

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

Ограничения

0 ≤ N, A_i ≤ 2 * 10⁹

1 ≤ S ≤ 100

Пояснения к примеру

100 / 25 = 4 ; 4 - 4 = 0

100 / 11 = 9 ; 9 / 11 = 0

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

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

100
6
4 7 10 5 25 11

2

Задача B6. Два измерения ≡

Условие

Ученые планируют провести важный эксперимент с использованием исследовательского модуля на планете X-2019. В процессе эксперимента будет проведено два измерения: основное и контрольное. Каждое измерение занимает ровно один час и должно начинаться спустя целое число часов после начала работы исследовательского модуля.

Данные эксперимента планируется немедленно передать на орбитальную станцию. Канал связи с орбитальной станцией будет установлен с l-го по r-й час от начала работы исследовательского модуля, включительно. Кроме того, согласно плану эксперимента между измерениями планета должна совершить целое число оборотов вокруг своей оси. Планета X-2019 осуществляет оборот вокруг своей оси за a часов.

Таким образом, если измерения осуществляются на i-м и j-м часу, то должно выполняться неравенство l ≤ i ≤ j ≤ r, а величина (j − i) должна быть кратна~a. Теперь учёным необходимо понять, сколько существует различных способов провести измерения.

Требуется написать программу, которая по заданным границам времени измерений l и r и периоду обращения планеты вокруг своей оси a определяет количество возможных способов провести измерения: количество пар целых чисел i и j, таких что l ≤ i ≤ j ≤ r, и величина (j − i) кратна a.

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

Входные данные содержат три целых числа, по одному на строке: l, r и a.

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

Выведите одно целое число: количество способов провести измерения.

Ограничения

1 ≤ l ≤ r ≤ 10⁹, 1 ≤ a ≤ 10⁹

Описание подзадач и системы оценивания

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

Пояснения к примерам

В первом примере можно провести измерения в следующие пары часов: (1, 3), (1, 5), (2, 4), (3, 5).

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

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

1
5
2

4

4
9
6

0

Задача B71. Шифр ≡

Условие

Отряд под командованием лейтенанта О’Денила нашел странный текст, который состоит из n пар целых неотрицательных чисел a, b с одинаковым количеством разрядов. Лейтенант понял, что текст зашифрован и передал его в штаб.

В штабе дешифровщики поняли, что для расшифровки текста необходимо, чтобы пары были отсортированы следующим образом: первые числа a - по возрастанию, а вторые b - по убыванию в случаях, где первые числа соответствующих пар равны т.е. там, где

a_i = a_j, i ≠ j, i, j = 1,2,3,…,n

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

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

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

В следующих n строках приводится n пар целых чисел a, b - перечень пар чисел для расшифровки.

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

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

Ограничения

2 ≤ n ≤ 10³

 − 10⁹ ≤ a, b ≤ 10⁹

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

3
1123 1325
6356 3731
6356 3738

1123 1325
6356 3738
6356 3731

Задача B72. Быстрая помощь ≡

Условие

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

Самолёты имеют различную скорость, так что самолёт номер i затратит на полёт в точности a_i минут. Разгрузка любого самолёта в аэропорту В занимает L минут, после чего аэропорт готов к приёму следующего самолёта.

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

Самолёты могут взлетать в любом порядке, но не должны обгонять друг друга в воздухе, т. е. если самолёт 1 взлетел раньше самолёта 2, то и приземлиться он должен раньше.

Требуется определить минимальное время в минутах, требуемое на перелёт и разгрузку всех самолётов.

Формат входного файла

Формат выходного файла

Ограничения

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

2 10
8 5

25

Задача B73. Гражданская оборона ≡

Условие

Штаб гражданской обороны Тридесятой области решил обновить план спасения на случай ядерной атаки. Известно, что все n селений Тридесятой области находятся вдоль одной прямой дороги. Вдоль дороги также расположены m бомбоубежищ, в которых жители селений могут укрыться на случай ядерной атаки.

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

Формат входного файла

Первая строка входного файла содержит число n — количество селений. Вторая строка содержит n различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го селения.

Третья строка входного файла содержит число m — количество бомбоубежищ. Четвертая строка содержит m различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го бомбоубежища.

Формат выходного файла

Выведите в выходной файл n чисел — для каждого селения выведите номер ближайшего к нему бомбоубежища. Бомбоубежища пронумерованы от 1 до m в том порядке, в котором они заданы во входном файле.

Ограничения

1 ≤ n, m ≤ 100000

Все расстояния положительны и не превышают 10⁹. Селение и убежище могут располагаться в одной точке.

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

4
1 2 6 10
2
7 3

2 2 1 1

Задача B74. Большой линейный коллайдер ≡

Условие

Группа ученых работает в международной научной лаборатории, которая занимается исследованиями поведения элементарных частиц в установке для экспериментов "Большой линейный коллайдер" (БЛК). Установка БЛК представляет собой прямую, в некоторых точках которой размещаются частицы, которые могут перемещаться вдоль прямой.

В очередном эксперименте в БЛК размещаются n частиц, каждая из которых представляет собой либо отрицательно заряженную частицу — электрон e⁻, либо положительно заряженную частицу — позитрон e⁺. В эксперименте i-я частица исходно размещается в точке с координатой x_i. После начала эксперимента в результате работы БЛК частицы начнут перемещаться в разные стороны вдоль прямой: e⁻ частицы перемещаются по направлению уменьшения координаты, а e⁺ частицы — по направлению увеличения координаты. Абсолютные величины скоростей всех частиц одинаковы и равны 1.

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

Ученые выбрали m различных моментов времени t₁, t₂, ..., t_m, для каждого из которых их интересует, какое количество частиц находится в БЛК непосредственно после каждого из этих моментов времени. Отсчет времени начинается с момента 0, когда частицы приходят в движение. Частицы, исчезнувшие в результате взаимодействия в момент времени t_j, не должны учитываться при подсчете количества частиц для этого момента времени.

Требуется написать программу, которая по описанию исходного расположения и типов частиц, а также заданным моментам времени, определяет для каждого из моментов количество частиц, которое будет находиться в БЛК непосредственно после этого момента.

Формат входного файла

Первая строка входного файла содержит число n — количество частиц. Последующие n строк описывают частицы следующим образом: каждая строка содержит по два целых числа x_i и v_i — координату i-й частицы и ее тип соответственно (x₁ < x₂ < x₃ < ...  < x_n). Частица e⁻ описывается значением v_i =  − 1, а частица e⁺ описывается значением v_i = 1.

Следующая строка содержит целое число m — количество моментов времени, которые выбрали ученые. Последняя строка содержит m целых чисел: t₁,t₂,...,t_m.

Формат выходного файла

Для каждого момента времени во входном файле требуется вывести одно число: количество частиц в БЛК непосредственно после этого момента.

Ограничения

1 ≤ n, m ≤ 200000

 − 10⁹ ≤ x_i, m ≤ 10⁹

0 ≤ t_i ≤ 10⁹

v_i равно  − 1 или 1

Описание подзадач и системы оценивания

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

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Пояснение к примеру

В приведенном примере в начальный момент в БЛК находятся 4 частицы: частица e⁺ в точке  − 1, частица e⁻ в точке 0, частица e⁺ в точке 1 и частица e⁻ в точке 5.

В момент времени 0.5 первая частица e⁺ и первая частица e⁻ сталкиваются в точке с координатой  − 0.5 и исчезают. В момент времени 1 оставшиеся две частицы находятся в точках с координатами 2 и 4, соответственно. В момент времени 2 они сталкиваются в точке 3 и исчезают. Больше в БЛК частиц нет.

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

4
-1 1
0 -1
1 1
5 -1
4
0 1 2 3

4
2
0
0

Задача B81. Cut the band ≡

Условие

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

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

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

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

Формат входного файла

Первая строка входного файла содержит целое число N — количество чисел на ленточке.

Вторая строка входного файла содержит N целых чисел a_i — последовательность чисел на ленточке.

Третья строка входного файла содержит целое число M — количество друзей Васи.

Четвертая строка входного файла содержит M целых чисел b_i — нелюбимое число i-го друга. Все b_i различны.

Формат выходного файла

Выходной файл должен содержать единственное целое число — минимальное количество разрезов ленточки.

Ограничения

1 ≤ N ≤ 10⁵

2 ≤ M ≤ 10⁵

1 ≤ a_i, b_i ≤ 10⁹

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

4
1 2 3 4
2
1 2

1

5
3 4 5 1 5
3
3 2 5

0

Задача B82. groupby group ≡

Условие

Необходимо написать программу, которая группирует студентов по их группам.

Формат входного файла

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

Группа и имя студента разделены символом табуляции.

Формат выходного файла

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

Сами группы следуют также в алфавитном порядке.

Ограничения

1 ≤ n ≤ 10⁵

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

3
M8103	Sidorov Sidor
M8888	Petrov Petr
M8103	Ivanov Ivan

M8103
Ivanov Ivan
Sidorov Sidor
M8888
Petrov Petr

Задача B84. Силовые поля ≡

Условие

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

Экспериментальная установка содержит квадратную платформу размером 10⁹ × 10⁹, заполненную плодородной почвой. Над платформой установлен источник излучения. Между источником излучения и платформой можно включать n силовых полей.

Генератор силовых полей установлен над точкой (0, 0). При этом i-е силовое поле представляет собой прямоугольник со сторонами, параллельными границам платформы и координатами двух противоположных углов (0, 0) и (x_i, y_i).

В эксперименте планируется изучать воздействие излучения на растения при облучении через k силовых полей. Из заданных n полей необходимо выбрать k полей для эксперимента. Ученые хотят выбрать силовые поля таким образом, чтобы площадь участка платформы, над которой находятся все k выбранных силовых полей, была максимальна.

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

Формат входного файла

Первая строка входного файла содержит целые числа n и k — общее количество силовых полей и количество силовых полей, которые необходимо выбрать для эксперимента.

Последующие n строк содержат по два целых числа x_i, y_i — координаты дальнего от начала координат угла прямоугольного участка i-го силового поля.

Формат выходного файла

Требуется вывести одно целое число: максимальную площадь искомого участка.

Ограничения

1 ≤ k ≤ n ≤ 200 000, 1 ≤ x_i, y_i ≤ 10⁹

Описание подзадач и системы оценивания

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

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Пояснение к примеру

На рис. 1 показаны пять силовых полей, заданных во входном файле. Оптимальный способ выбрать из них три поля для эксперимента показан на рис. 2.

Рис 1. Силовые поля в примере описания входных данных.

Рис 2. Оптимальный выбор трех из пяти силовых полей в данном примере.

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

5 3
3 5
2 2
2 5
4 4
5 3

9

Задача C. Многократное суммирование ≡

Условие

Дан массив целых чисел a₁, a₂, ..., a_N и дано M команд типа "найти сумму чисел a_i для i от l до r".

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

Формат входного файла

Входной файл содержит целое число N, за которым следуют N целых чисел a_i.

Далее во входном файле содержится целое число M, за которым следуют M пар целых чисел l_j r_j.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 1000000

1 ≤ M ≤ 1000000

 − 1000 ≤ a_i ≤ 1000

1 ≤ l_j ≤ r_j ≤ N

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

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

6 14 12

Задача D1. Финальный босс ≡

Условие

Мальчик Коля дошёл в своей любимой игре до финального босса.

С помощью игровой подсказки Коля узнал механику босса.

• Изначально у босса H единиц здоровье.
• Победить босса нужно за M минут или меньше.
• За минуту Коля наносит D урона.
• Каждую минуту (после того как Коля нанёс D урона) здоровье босса увеличивается в 1,1 раза (знаки после запятой убираются) и ещё прибавляется 10 единиц здоровья.

Необходимо узнать какой минимальный урон Коле нужно наносить по финальному боссу, чтоб его одолеть за M минут.

Формат входного файла

Входной файла содержит целые числа H M.

Формат выходного файла

Выходной файл должен содержать единственное целое число — минимальный подходящий урон в минуту.

Ограничения

1 ≤ H ≤ 10⁹; 1 ≤ M ≤ 10⁴

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

100 5

32

30 4

16

Задача D2. Вырубка леса ≡

Условие

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

Дмитрий срубает по A деревьев в день, но каждый K-й день он отдыхает и не срубает ни одного дерева. Таким образом, Дмитрий отдыхает в K-й, 2K-й, 3K-й день, и т.д.

Федор срубает по B деревьев в день, но каждый M-й день он отдыхает и не срубает ни одного дерева. Таким образом, Федор отдыхает в M-й, 2M-й, 3M-й день, и т.д.

Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не отдыхает, они срубают A + B деревьев, в дни, когда отдыхает только Федор — A деревьев, а в дни, когда отдыхает только Дмитрий — B деревьев. В дни, когда оба лесоруба отдыхают, ни одно дерево не срубается.

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

Требуется написать программу, которая по заданным целым числам A, K, B, M и X определяет, за сколько дней все деревья в лесу будут вырублены.

Пояснения к примеру

В приведенном примере лесорубы вырубают 25 деревьев за 7 дней следующим образом:

• 1-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 5 деревьев;
• 2-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 10 деревьев;
• 3-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 12 деревьев;
• 4-й день: Дмитрий отдыхает, Федор срубает 3 дерева, итого 15 деревьев;
• 5-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 20 деревьев;
• 6-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 22 дерева;
• 7-й день: Дмитрий срубает 2 дерева, Федор срубает оставшееся 1 дерево, итого все 25 деревьев срублены.

Внимание! Тест из примера не подходит под ограничения для подзадач 2 и 3, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест даже, если оно рассчитано на решение только каких-либо из подзадач 2 и 3.

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

Подзадача 1 (32 баллов)

1 ≤ X ≤ 1000, 1 ≤ A, B ≤ 1000, 2 ≤ K, M ≤ 1000.

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

Подзадача 2 (10 баллов)

1 ≤ X ≤ 10¹⁸; X < K; X < M.

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

Подзадача 3 (10 баллов)

1 ≤ X ≤ 10¹⁸.

Дополнительно к приведенным ограничениям выполняется условие K = M. Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 4 (48 баллов)

1 ≤ X ≤ 10¹⁸, 1 ≤ A, B ≤ 10⁹, 2 ≤ K, M ≤ 10¹⁸.

В этой подзадаче 16 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Формат входного файла

Входной файл содержит пять целых чисел, разделенных пробелами: A, K, B, M и X.

Формат выходного файла

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

Ограничения

1 ≤ A, B ≤ 10⁹, 2 ≤ K, M ≤ 10¹⁸, 1 ≤ X ≤ 10¹⁸

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

2 4 3 3 25

7

Задача D3. Дипломы ≡

Условие

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось N дипломов, причем, как оказалось, все они имели одинаковые размеры: W — в ширину и H — в высоту.

Сейчас Петя учится в одном из лучших российских университетов и живет в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить ее к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещен строго в прямоугольнике размером W на H. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек.

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

Система оценивания

Решения, правильно работающие только при W, H, N ≤ 1000, будут оцениваться в 40 баллов.

Формат входного файла

Входной файл содержит три целых числа: W, H, N

Формат выходного файла

В выходной файл необходимо вывести ответ на поставленную задачу.

Ограничения

1 ≤ W, H, N ≤ 10⁹

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

2 3 10

9

Задача E1. Сумма ≡

Условие

Дан массив из N элементов, нужно научиться находить сумму чисел на отрезке.

Формат входного файла

Первая строка содержит два целых числа N и K — число чисел в массиве и количество запросов. (1 ≤ N ≤ 100 000), (0 ≤ K ≤ 100 000). Следующие K строк содержат запросы

• A i x — присвоить i-му элементу массива значение x (1 ≤ i ≤ n, 0 ≤ x ≤ 10⁹)
• Q l r — найти сумму чисел в массиве на позициях от l до r. (1 ≤ l ≤ r ≤ n)

Формат выходного файла

На каждый запрос вида Q l r нужно вывести единственное число — сумму на отрезке.

Ограничения

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

5 9
A 2 2
A 3 1
A 4 2
Q 1 1
Q 2 2
Q 3 3
Q 4 4
Q 5 5
Q 1 5

0
2
1
2
0
5

Задача E2. Дипломы 2.0 ≡

Условие

Сегодня в ДВФУ состоится традиционное вручение дипломов выпускникам института математики и компьютерных наук. Каждый год это особенное событие и большой праздник, как для выпускников, так и для сотрудников факультета, своеобразное подведение итогов совместного многолетнего труда.

В этом году из института выпускается n студентов. Еще давным-давно, при поступлении, каждому студенты был выдан порядковый номер, который зависел от их места в конкурсном списке по результатам вступительных испытаний. Те, кто были выше в конкурсном списке, имели более низкий порядковый номер. То есть, если человек сдал вступительные лучше всех, то имел 1-й порядковый номер, кто сдал чуть хуже этого человека, но лучше всех остальных — 2-й, и так далее. Хоть это и было очень давно, эти номера закрепились за ними до конца их учебных дней.

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

Во время начала церемонии декану вручили список, по которому он должен выдавать дипломы. i-й по счету диплом должен быть выдан студенту под порядковым номером a_i. Так как укладывали все дипломы до получения этого списка, расположение их не такое, как должно быть. Они решили действовать по следующей тактике: вытаскивать дипломы по-очереди до того момента, пока не достанут нужный, и складывать все выложенные дипломы в том же порядке, как они и лежали. Т.е. если нужно достать диплом под номером 4, то сначала необходимо выложить дипломы 6 и 5 (или 1, 2 и 3, так как бокс имеет отверстия с двух сторон), а затем сложить их обратно в том же порядке. После того, как диплом выдан, он пропадает из бокса. На каждую операцию взятия и складывания дипломом затрачивается одно действие. Такая тактика, кстати, выбрана не просто так, они хотят ускорить выдачу дипломов и при этом не запутаться.

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 2 ⋅ 10⁵

1 ≤ a_i ≤ n

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

6
4 3 5 2 1 6

18

2
2 1

2

5
1 2 3 4 5

5

6
5 3 6 2 4 1

14

Задача E3. RMQ ≡

Условие

• «max l r». Найти максимум в массиве a от l-ой ячейки до r-ой включительно.
• «add l r v». Прибавить значение v к каждой ячейке a[] от l-ой до r-ой включительно.

Формат входного файла

Первая строка содержит два целых числа n и q (1 ≤ n, q ≤ 10⁵) — длина массива и число запросов соответственно.

Вторая строка содержит n целых чисел a₁, …, a_n (|a_i| ≤ 10⁵), задающих соответствующие значения массива.

Следующие q строк содержат запросы.

В зависимости от типа запрос может иметь вид либо «max l r», либо «add l r v».

1 ≤ l ≤ r ≤ n, |v| ≤ 10⁵.

Формат выходного файла

Для каждого запроса вида «max l r» требуется в отдельной строке выдать значение соответствующего максимума.

Ограничения

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

5 3
1 2 3 4 -5
max 1 3
add 1 2 5
max 1 3

3
7

Задача E4. Сумма+присвоение на отрезке ≡

Условие

Формат входного файла

Первая строка входного файла содержит два целых числа N и K — число чисел в массиве и количество запросов. (1 ≤ N ≤ 100 000), (0 ≤ K ≤ 100 000). Следующие K строк содержат запросы:

• A l r x

   — присвоить элементам массива с позициями от l до r значение x (1 ≤ l ≤ r ≤ N, 0 ≤ x ≤ 10⁹)

• Q l r

   — найти сумму чисел в массиве на позициях от l до r. (1 ≤ l ≤ r ≤ N)

Изначально массив заполнен нулями.

Формат выходного файла

На каждый запрос вида

Q l r

Ограничения

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

5 9
A 2 3 2
A 3 5 1
A 4 5 2
Q 1 3
Q 2 2
Q 3 4
Q 4 5
Q 5 5
Q 1 5

3
2
3
4
2
7

Задача E5. Плакаты ≡

Условие

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

Для того, чтобы приветствовать команду, n друзей встанут в круг. Пронумеруем их от 1 до n в порядке их расположения по кругу. Таким образом, для всех i от 1 до n − 1 друзья с номерами i и i + 1 стоят рядом, также рядом стоят друзья с номерами n и 1. У каждого из друзей есть плакат. Каждый плакат характеризуется своей красочностью — целым неотрицательным числом. Плакат у друга с номером i имеет красочность a_i.

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

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

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

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

Первая строка ввода содержит целое число n (4 ≤ n ≤ 40 000) — количество друзей.

Вторая строка содержит n целых чисел a_i (0 ≤ a_i ≤ 10⁹) — исходные значения красочности плакатов у друзей.

Третья строка содержит одно целое число q (0 ≤ q ≤ 40 000) — количество изменений плакатов, которые вносили друзья.

Каждая из следующих q строк содержит два целых числа p_i и v_i (1 ≤ p_i ≤ n; 0 ≤ v_i ≤ 10⁹) — номер друга, плакат которого изменился, и новая красочность этого плаката.

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

Выведите q + 1 число. Перед первым изменением, а также после каждого изменения плакатов выведите одно целое число — максимальное суммарное значение красочности поднятых плакатов, если нельзя поднимать больше трёх плакатов подряд.

Ограничения

4 ≤ n ≤ 40 000

0 ≤ a_i ≤ 10⁹

0 ≤ q ≤ 40 000

1 ≤ p_i ≤ n; 0 ≤ v_i ≤ 10⁹

Система оценивания

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

Пояснения

Перед первым изменением плакаты следует поднять друзьям с номерами 2, 4, 5, 6. Суммарная красочность поднятых плакатов будет равняться 17.

После первого изменения плакат друга с номером 6 имеет красочность 0. Теперь плакаты следует поднять друзьям с номерами 1, 3, 4, 5. Суммарная красочность будет равняться 13.

После второго изменения плакат друга с номером 2 имеет красочность 5. Плакаты следует поднять друзьям с номерами 1, 2, 4, 5. Суммарная красочность будет равняться 15.

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

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

17
13
15

Задача F1. Питание программистов ≡

Условие

Оргкомитет сборов по программированию знает, что важно организовать правильное питание участников. Еда должна быть вкусной, а блюда — разнообразными. Поэтому разработку меню доверили повару тёте Вале.

Тётя Валя умеет готовить несколько разных блюд. Она использует для их обозначения маленькие английские буквы. Всего в течение сборов будет n приёмов пищи. Тётя Валя составила черновик меню — строку s, состоящую из n маленьких английских букв. Символ s_i обозначает блюдо, которое она запланировала для i-го приёма пищи.

Черновик меню полностью сбалансирован по всем питательным компонентам, но тётя Валя не особо заботилась о разнообразии.

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

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

Формат входного файла

Входной файл содержит строку s, состоящую из маленьких букв английского алфавита — черновик меню.

Формат выходного файла

Выходной файл должен содержать единственную строку — окончательный вариант меню.

Ограничения

1 ≤ n ≤ 100000;

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

olmkoo

moloko

Задача F2. Хоттаб-share/2 ≡

Условие

Прожив 1000 лет, Гассан Абдуррахман ибн Хоттаб узнал, что из интернета можно скачивать файлы. Решив помочь другим пользователям, он сотворил собственный сервер с файлами. Поскольку сервер Хоттаба волшебный, любой файл скачивается с него мгновенно. Однако, после скачивания файла размером S мегабайт скачавший его компьютер отключается от сервера на S секунд.

В распоряжении шушанчиков имеется один компьютер, подключённый к интернету. Им требуется скачать N файлов, i-й файл размером s_i мегабайт. Шушанчики просят Вас рассчитать минимальное время, за которое можно скачать эти файлы с сервера Хоттабыча.

Формат входного файла

Во входном файле содержится число N — количество файлов, за которым следуют N чисел s_i — размеры файлов в мегабайтах.

Формат выходного файла

В выходном файле должно содержаться единственное число — минимальное время скачивания всех файлов в секундах.

Ограничения

1 ≤ N ≤ 1000

1 ≤ s_i ≤ 1000

Все числа во входном файле целые

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

2
13 17

13

5
13 19 17 14 19

63

Задача F3. Текст ≡

Условие

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

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

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

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

Формат входного файла

Первая строка входного файла содержит натуральное число k — максимально допустимая длина строки.

Вторая строка входного файла содержит текст, который необходимо вывести. Текст состоит из латинских букв, цифр, пробелов и символов "," (запятая), "." (точка), "!" (восклицательный знак) и "?" (вопросительный знак).

Формат выходного файла

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

Ограничения

1 ≤ k ≤ 100. Размер входного файла не превышает 50000 байтов.

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

22
This     is a sample text!

This is a sample text!

12
This     is a sample text!

This is a
sample text!

Задача F4. Арифметическая прогрессия ≡

Условие

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

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

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

Формат входного файла

Входной файл содержит целое число N — количество чисел, за которым следуют N целых чисел a_i.

Формат выходного файла

Выходной файл должен содержать целое число M — количество чисел, которые останутся после вычёркивания (при этом количество вычеркнутых чисел должно быть минимальным).

Далее должны следовать M целых чисел — номера чисел, которые останутся после вычёркивания, перечисленные в порядке возрастания.

Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 100

1 ≤ a_i ≤ 10⁶

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

7
1 3 4 2 7 8 10

4
1 3 5 7

Задача F5. Мёд и справедливость ≡

Условие

Две пчелы собирают пыльцу с N цветков, расположенных в ряд. Цветок номер i содержит a_i микрограмм пыльцы.

Пчёлы договорились, что первая пчела будет собирать пыльцу с цветков на участке от L до M включительно, а вторая  — от M + 1 до R включительно (L ≤ M < R). Чтобы ни одной из пчёл не было обидно, сумма запасов пыльцы на первом и втором участках пчёл должны совпадать.

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

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

Входные данные содержат целое число N, за которым следует N чисел a_i.

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

Выходные данные должны содержать целые числа L M R — границы участков. Если оптимальных решений несколько, выведите решение с наименьшим значением L. Если решения не существует, выведите единственное число  − 1.

Ограничения

2 ≤ N ≤ 10000

1 ≤ a_i ≤ 10⁵

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

3
1 1 2

1 2 3

2
2 5

-1

Задача G1. Длинный дом ≡

Условие

Две подруги, Нина и Марина, живут квартирах n и m в одном подъезде самого длинного дома в мире. Каким может быть наибольший номер этого подъезда? Количество квартир в каждом подъезде одинаково.

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

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

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

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

1 ≤ m < n ≤ 10⁹

Пояснение к примеру

В примере дано n = 52 и m = 41. Эти квартиры могут находиться в первом подъезде (если в одном подъезде квартир не меньше, чем 52).

Эти квартиры могут находиться во втором подъезде (если в одном подъезде квартир не меньше, чем 26 и не больше, чем 40).

Эти квартиры могут находиться в третьем подъезде (если в одном подъезде квартир не меньше, чем 18 и не больше, чем 20).

Эти квартиры могут находиться в четвертом подъезде (если в одном подъезде ровно 13 квартир).

Эти квартиры не могут находиться в подъезде с номером большим, чем 4. Ответ на вопрос задачи — 4.

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

52
41

4

Задача G2. Emitting light ≡

Условие

Юный физик Маша изучает лазеры. Маша хочет построить простой двумерный волновод, состоящий из двух очень длинных параллельных зеркал. Первое зеркало совпадает с осью Ox, а второе зеркало расположено на расстоянии h от первого.

Маша расположила лазер в точке с координатами (0,y) и направила лазерный луч в направлении (1,  − 1). Маша хочет подобрать расстояние между зеркалами h так, чтобы луч прошёл через точку с координатами (x_t,y_t). Сам лазер при этом должен находиться внутри волновода, то есть h ≥ y. Лазерный луч всегда отражается от зеркал под углом в 45 градусов.

Формат входного файла

Входной файл содержит три целых числа: y, x_t, y_t — координаты лазера и цели.

Формат выходного файла

Программа должна вывести единственное целое число — значение h, при котором лазерный луч пройдёт через цель. Если есть несколько решений, выведите минимальное возможное значение h. Если решений нет, выведите одно число  − 1.

Ограничения

1 ≤ y, x_t, y_t ≤ 10⁹

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

5 2 2

-1

5 6 1

5

2 16 2

2

Задача G3. Загадочное уравнение ≡

Условие

Маленький Вася очень любит уравнения. Однажды ему на глаза попалось уравнение x + y + xy = n. Вася захотел узнать количество пар целых неотрицательных чисел x и y, которые являются решениями этого уравнения.

Так как Вася еще маленький, то он попросил вас посчитать это количество.

Формат входного файла

В единственной строке входного файла дано число n (0 ≤ n ≤ 10⁹).

Формат выходного файла

В единственную строку выходного файла выведите ответ на задачу.

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

5

4

8

3

Задача G4. Потерянное число ≡

Условие

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

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

Формат входного файла

В первой строке входные данные содержат число N - количество листков с числами, которое собрал Игорь.

В следующей строке содержатся N чисел a_i разделенные пробелами

Формат выходного файла

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

Ограничения

2 ≤ N ≤ 10⁶

0 ≤ a_i ≤ 10⁷

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

4
4 6 10 2

8

Задача G5. Fractional multiplication ≡

Условие

Имеется набор из N рациональных дробей, каждая из которых задается своим числителем A_i и знаменателем B_i.

Требуется написать программу, которая выводит:

• 0 — если произведение всех этих дробей дает единицу либо простое число;
• 1 — если это составное целое число;
• 2 — если это дробное число.

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

Входные данные содержит целое число N, за которым следует набор из N пар целых чисел (A_i, B_i).

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

Выходные данные должны содержать единственное число — ответ задачи.

Ограничения

1 ≤ N ≤ 200, 1 ≤ (A_i, B_i) < 2³²

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

1
35880 17940

0

1
76824 12804

1

1
94803 11573

2

Задача G6. Полные квадраты ≡

Условие

С целью поиска закономерностей иногда полезно сгенерировать длинную последовательность по определенным правилам. Известно, например, что последовательность 0, 0 + 1, 0 + 1 + 3, 0 + 1 + 3 + 5, …, 0 + 1 + 3 + …  + (2n − 1), …, составленная из сумм нескольких первых нечетных натуральных чисел, состоит из квадратов целых чисел: 0, 1, 4, 9, …, n²,….

Обобщим эту последовательность следующим образом: будем использовать вместо начального значения не ноль, а число k. Получим последовательность: k, k + 1, k + 1 + 3, k + 1 + 3 + 5, …, k + 1 + 3 + …  + (2n − 1), …. В отличие от случая k = 0, в этой последовательности могут встречаться не только полные квадраты. Необходимо найти минимальное целое неотрицательное число, квадрат которого встречается в этой последовательности.

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

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

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

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

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

Ограничения

 − 10¹² ≤ k ≤ 10¹²

Описание подзадач и системы оценивания

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

Пояснения к примерам

В первом примере каждое число последовательности является полным квадратом. Минимальный из них — 0, 0² = 0.

Во втором примере последовательность начинается так:  − 5,  − 4,  − 1, 4, 11, 20,…. Минимальное неотрицательное целое число, квадрат которого встречается в последовательности — 2, 2² = 4.

В третьем примере последовательность начинается так: 2, 3, 6, 11, 18, …. В ней нет квадратов целых чисел.

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

0

0

-5

2

2

none

Задача G7. Большая распродажа ≡

Условие

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

1) На товар можно установить любую скидку (от 1 до 99 процентов) по сравнению с ценой товара в предыдущий день.

2) И скидка, и новая стоимость товара должны являться натуральными числами.

Например, если товар стоит 20 рублей, на него можно установить скидку 25% и на следующий день этот товар будет продаваться по 15 рублей. А вот скидку в 30% установить нельзя — новая цена будет выражаться дробным числом рублей.

Молодой программист Тимофей каждый день после работы заходит в магазин и скупает все товары, которые сегодня стоят 1 рубль. Как скоро хозяину магазина удастся снизить стоимость товара с n рублей до 1 рубля?

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

Единственная строка входных данных содержит натуральное число n — начальная стоимость товара в рублях. Гарантируется, что это значение таково, что существует последовательность корректных скидок, снижающих стоимость товара до 1 рубля.

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

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

Ограничения

2 ≤ n ≤ 10¹⁸

Пояснение к примеру

В примере дана начальная стоимость товара 125 рублей. В первый день на него устанавливается скидка 96% и товар продается по цене 5 рублей. Во второй день скидка составит 80% и вечером товар будет куплен Тимофеем за 1 рубль.

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

125

2

Задача G8. Current year problem ≡

Условие

Найдите наименьшее положительное целое число, которое делится на n и начинается с цифр 2021 в десятичной записи.

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

Входные данные содержат единственное целое число n — делитель искомого числа.

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

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

Ограничения

1 ≤ n ≤ 10¹²

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

2022

20211912

Задача G9. Arithmetic pairs ≡

Условие

Требуется подсчитать общее количество пар целых чисел (p, n) таких, что p ≥ 1, n > 1 и A ≤ pⁿ ≤ B.

Формат входного файла

Входной файл содержит два натуральных числа: A и B.

Формат выходного файла

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

Ограничения

2 ≤ A ≤ B < 2⁶³

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

10 100

13

37 48

0

Задача H1. Марфа Геннадьевна в столовой ≡

Условие

Однажды Марфа Геннадьевна пришла в столовую. В меню было N блюд. Блюдо с номером i стоит c_i рублей. Для каждого блюда известен также коэффициент сытости блюда — a_i.

Марфа Геннадьевна знает, что для того, чтобы наесться, нужно, чтобы сумма коэффициентов сытости съеденных блюд была не меньше A.

Какие блюда нужно взять в столовой, чтобы наесться и потратить как можно меньше денег? Обратите внимание, что Марфа Геннадьевна может взять более одной порции блюда (любое целое неотрицательное число порций).

Формат входного файла

Входной файл содержит целые числа N A.

Далее следуют N пар целых чисел c_i a_i.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 100

1 ≤ A ≤ 1000

1 ≤ c_i ≤ 500

1 ≤ a_i ≤ 100

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

3 10
2 1
5 4
6 6

11

4 32
1 8
2 4
3 2
4 1

4

Problem H2. Hall of water life ≡

Statement

The main hall of the Nearsea Institute of Unspecified Underwater Studies has a shape of a long corridor. Along the corridor, there are N aquariums exhibiting various sea creatures. Aquariums are located at distances x₁, …, x_N from the hall entrance (x_i < x_i + 1).

The institute has recently got a new director, who decided that the aquarium maintenance is too costly, and issued an order to remove M (0 ≤ M ≤ N − 2) aquariums.

To minimize the disruption to the looks of the hall, it was decided that:

1. the first and the last aquariums should be left in their places;
2. the maximum distance between the adjacent aquariums must be as small as possible.

Your program must select aquariums for removal in such a way that the above conditions are satisfied.

Input file format

Input file contains integers N M followed by N integers x_i.

Output file format

Output file should contain a single integer — the smallest possible maximum distance.

Constraints

Sample tests

5 2
1 2 3 4 5

2

4 1
10 21 30 40

19

Задача H3. Рассадка пассажиров ≡

Условие

Илон Маск закончил создание транспорта будущего — Hyperloop. Hyperloop — расположенный на опорах надземный трубопровод, внутри которого с высокой скоростью в одном направлении перемещаются одиночные транспортные капсулы. Пассажирский вариант предполагает n рядов по одному сиденью. Однако из-за конструктивных недостатков люди не могут сидеть на двух подряд идущих рядах. Поэтому, когда продаётся билет с номером места a_i из продажи исчезает сам этот билет, и два соседних с ним билета.