Задача 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

Problem E. Автономная охрана ≡

Statement

Young programmer Vasya tinkered with robots, and decided to create a new startup Delta Security with the goal of producing robot guardian to replace human guards.

As a first step, he considered a single wall and two patrolling robots moving back and forth along it.

First robot patrols a segment from L₁ to R₁ meters. Second robot patrols a segment from L₂ to R₂ meters.

At the start, each robot is located at the leftmost point of its segment and is facing to the right.

Each second, every robot checks whether it has reached the edge of its segment. In that case, robot reverses its direction. Then, robot moves exactly 1 meter in its current direction. Robots continue to patrol indefinitely. All robots move simultaneously.

You task is to determine maximum possible distance between two robots.

Robots could be located in the same position on the wall. This case doesn't affect their movements.

Input file format

Input file contains integers L₁ R₁ L₂ R₂.

Output file format

Output file must contain a single integer — maximum distance between robots.

Constraints

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

L₁ < R₁, L₂ < R₂

Sample tests

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