Задача A. Бада развешивает зоков ≡

Условие

N зоков испачкались в меду, и бада их постирал. Теперь зоков нужно развесить на верёвки сушиться. Верёвок у бады много (неограниченное количество). На каждой из них может уместиться не более M зоков. Каждого зока нужно подвесить прищепками за оба уха. Если два зока висят рядом, то их соседние уши можно зажать одной прищепкой.

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

В первом примере, приведённом ниже, двоих зоков можно повесить рядом. Для этого хватит 3 прищепок.

Во втором примере в ряд можно повесить троих зоков (на это уйдёт 4 прищепки), а четвёртого зока повесить на другую верёвку, использовав ещё 2 прищепки. Можно также повесить зоков на двух верёвках по два зока на каждой, также использовав в сумме 6 прищепок.

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

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

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

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

Ограничения

1 ≤ N, M ≤ 10⁶

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

2 2

3

4 3

6

Задача B. Точки на окружности ≡

Условие

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

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

В первой строке записано одно целое число N — количество точек на окружности.

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

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

Ограничения

1 ≤ N ≤ 10⁹

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

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

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

3

2

4

2

Задача C. Брокер ≡

Условие

Брокер Лёша решил подзаработать, для чего собирается совершить N звонков в разные банки. Стратегия Лёши проста: он просит у очередного банка деньги и иногда их получает. Банк под номером i может выдать брокеру ровно m_i денег и делает это только в том случае, если у брокера на момент звонка уже есть r_i денег на счету. С самого начала на счету брокера содержится A денег.

Очередной звонок происходит так: Лёша тратит t_i секунд на то, чтобы выяснить, сколько и при каких условиях банк может дать ему денег. Каждая секунда разговора по телефону стоит ему C денег.

Если счет брокера удовлетворяет условию банка, и если самому брокеру выгодно продолжать разговор, он тратит дополнительно t_i секунд на совершение сделки и вежливое завершение разговора, после чего ему на счет поступает m_i денег. В ином случае Лёша мгновенно отменяет сделку, бросает трубку и получает от банка 0 денег.

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

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

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

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

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

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

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

Ограничения

0 ≤ N ≤ 10²

0 ≤ A, C, r_i, m_i ≤ 10⁴

1 ≤ t_i ≤ 10³

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

3 1000 10
10 500 1000
1000 0 20
5 2000 8400

100

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

Условие

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

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 10⁶

0 ≤ a_i ≤ 10⁷

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

4
4 6 10 2

8

Задача E. Автономная охрана ≡

Условие

Юный программист Вася возился с роботами и решил основать стартап "Автономная охрана", цель которого — производство роботов-охранников, чтобы заменить людей-охранников.

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

Первый робот патрулирует отрезок от L₁ до R₁ метров от начала стены. Второй робот патрулирует отрезок от L₂ до R₂ метров.

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

Каждую секунду каждый робот проверяет, достиг ли он конца своего сегмента. В этом случае робот меняет свое направление на противоположное и сдвигается на 1 метр в текущем направлении. Роботы продолжают патрулировать бесконечно долго. Все роботы двигаются одновременно.

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

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

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

Входной файл содержит целые числа L₁ R₁ L₂ R₂.

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

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

Ограничения

0 ≤ L₁ < L₂ ≤ 10⁹, 0 ≤ R₁ < R₂ ≤ 10⁹

L₁ < R₁, L₂ < R₂

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

5 10
7 12

2

1 5
8 9

7

Задача F. Подвижный манипулятор ≡

Условие

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

Имеется манипулятор, состоящий из 2-х звеньев (костей), управляемых моторами. Моторы могут поворачиваться на некоторый положительный угол, заданный в радианах. Требуется, получив на вход координаты (x₀, y₀), определить, на сколько радиан нужно повернуть каждый из моторов, чтобы манипулятор занял указанную позицию. Начало отсчета координат — крепление первой кости. Длины и углы поворота каждой из костей ограничены.

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

Входной файл содержит набор вещественных чисел:

R₁, R₂ — размеры 1-й и 2-й кости;

F₁, F₂ — максимальный раствор угла для каждой из костей;

x₀, y₀ — координаты назначения.

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

Выходной файл должен содержать вещественные значения φ₁, φ₂ — углы поворота для каждого из моторов, указанные с точностью не менее 5 знаков после запятой.

Если решение не может быть найдено, вывести -1.

Ограничения

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

10 > R₁ ≥ R₂ > 0, π  > (F₁, F₂) > 0,

x₀ ∈ [ − 10, 10], y₀ ∈ [0, 10]

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

 0.50000  0.25000  3.14159  3.14159  0.50000  0.50000

 0.54936
 2.41886

 0.50000  0.50000  3.14159  3.14159 -0.75000  0.75000

-1

Задача G. Тяжелая химия 2 ≡

Условие

Данная задача является интерактивной.

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

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

Никита понимает, что демонстрация не будет достаточно эффектной, если атом будет весить очень мало, а он положит на весы слишком много гирек. Поэтому он хочет использовать не более ⌈ log₂(N)⌉  + 10 гирек. Помогите Никите определить вес атома.

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

Чтобы положить гирьку, ваша программа должна вывести запрос "L X" или "R X", где X — вес гирьки, которую Никите нужно положить на соответствующую чашу весов. После каждого запроса программа жюри ответит одним из символов " < ", " > " или " = ", если в результате добавления гирьки правая чаша перевесит, левая чаша перевесит или веса чаш сравняются соответственно.

Когда ваша программа определит вес атома, она должна вывести "! N" и завершиться.

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

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

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

Ограничения

1 ≤ N, X ≤ 2⁵⁵

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

В первом примере суммарный вес на чашах изменялся следующим образом: (5, 0), (5, 4), (5, 8), (11, 8), (11, 12), (12, 12).

Всего в первом примере решение могло использовать не более ⌈ log₂(5)⌉  + 10 = 13 гирек.

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

>

<

>

<

=

R 4

R 4

L 6

R 4

L 1

! 5

<

>

R 14

L 2

! 13

Задача H. Киберспортивный турнир ≡

Условие

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

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

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

Первая строка входного файла содержит числа N и M. Следующие M строк содержат пары чисел a_i и b_i. Гарантируется, что не существует такой пары i и j, что a_i = b_j и b_i = a_j.

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

Если невозможно провести турнир так, как хочет Влад, необходимо вывести No. Иначе первая строка выходного файла должна содержать Yes, а следующие далее N − 1 строк — описание матчей в порядке их проведения. По два числа на строку: первое число — номер победившего в очередном матче игрока, второе число — номер проигравшего игрока. Если существует несколько правильных ответов, выведите любой из них.

Ограничения

2 ≤ N ≤ 100000, 0 ≤ M ≤ 500000, 1 ≤ a_i, b_i ≤ N

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

3 3
1 2
2 3
3 1

Yes
1 2 
3 1

5 4
1 2
2 3
3 4
4 5

Yes
4 5
3 4
2 3
1 2

4 2
1 2
3 4

No

2 0

No

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

Yes
3 4
2 3
1 2

7 8
1 2 
2 3
3 1
4 1
4 5
5 6
6 7
7 5

Yes
2 3
1 2
4 1
6 7
5 6
4 5

Задача I. Геройская армия ≡

Условие

Слон Пахом любит играть в игру "Герои меча и магии". У Пахома есть N героев. У каждого героя в армии содержится ровно 7 различных видов существ (существ одного вида может быть много). Всего в игре существует 14 различных существ (7 видов, 1-го или 2-го уровня). У каждого существа есть сила p_i. Существа первого и второго уровня считаются различными, и их нельзя объединять без предварительного улучшения существ 1-го уровня до 2-го. Сила существа второго уровня не меньше силы того же существа первого уровня. Существа первого уровня обозначаются маленькими буквами латинского алфавита (a, b, c, d, e, f, g), второго — большими буквами латинского алфавита (A, B, C, D, E, F, G). Любое существо 1-го уровня можно улучшить до 2-го уровня потратив c_i денег. Пахому лень разделять группы существ, поэтому он может улучшить группу существ в какой либо армии только полностью. Улучшения происходят следующим образом a->A, b->B, c->C и т.д.

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

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

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

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

Вторая строка содержит 14 чисел p_i, мощность одного существа видов a, b, c, d, e, f, g, A, B, C, D, E, F, G. соответственно.

Третья строка содержит 7 чисел с_i, стоимость улучшения одного существа видов a, b, c, d, e, f, g, соответственно.

Далее следует N строк, каждая строка содержит 7 пар, t_ij q_ij — вид существа и количество существ этого вида у i-го героя.

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

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

Ограничения

1 ≤ N ≤ 50

0 ≤ M ≤ 5000

0 ≤ p_i, c_i, q_i ≤ 1000

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

2 10
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1
a 5 b 5 c 6 d 6 e 6 f 7 g 8
A 10 B 10 C 10 D 10 E 10 F 10 G 10

80

2 50 
0 1 2 3 4 5 6 1 2 3 4 5 6 7
1 1 1 1 1 1 1
A 10 B 20 C 30 D 40 E 50 F 60 G 70
a 400 B 300 C 100 D 100 E 100 F 400 G 500

9100

3 50 
0 1 2 3 4 5 6 1 2 3 4 5 6 7
1 1 1 1 1 1 1
a 1000 b 500 c 0 d 0 e 0 f 0 g 0
A 10 B 20 C 30 D 40 E 50 F 60 G 70
a 400 B 300 C 100 D 100 E 100 F 400 G 500

9590

Задача J. Несоседние буквы ≡

Условие

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

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

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

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

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

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

Ограничения

0 < |S| ≤ 10⁶

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

abc

-1

abbcd

cadbb