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

Автор:И. Туфанов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N, M ≤ 106

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 2
3
2
4 3
6

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

Автор:А. Жильцов, А. Усманов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Ограничения

1 ≤ N ≤ 109

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
2
2
4
2

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

Автор:А. Щуров   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:512 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

0 ≤ N ≤ 102

0 ≤ A, C, ri, mi ≤ 104

1 ≤ ti ≤ 103

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 1000 10
10 500 1000
1000 0 20
5 2000 8400
100

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

Автор:Гусаров В.Е.   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:512 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 106

0 ≤ ai ≤ 107

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
4 6 10 2
8

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

Автор:М. Спорышев, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

Первый робот патрулирует отрезок от L1 до R1 метров от начала стены. Второй робот патрулирует отрезок от L2 до R2 метров.

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

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

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

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

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

Входной файл содержит целые числа L1 R1 L2 R2.

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

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

Ограничения

0 ≤ L1 < L2 ≤ 109, 0 ≤ R1 < R2 ≤ 109

L1 < R1, L2 < R2

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5 10
7 12
2
2
1 5
8 9
7

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

Автор:А. Баранов, Д. Горячкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

R1, R2 — размеры 1-й и 2-й кости;

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

x0, y0 — координаты назначения.

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

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

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

Ограничения

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

10 > R1 ≥ R2 > 0, π > (F1, F2) > 0,

x0 ∈ [ − 10, 10], y0 ∈ [0, 10]

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

Входной файл (input.txt) Выходной файл (output.txt)
1
 0.50000  0.25000  3.14159  3.14159  0.50000  0.50000
 0.54936
 2.41886
2
 0.50000  0.50000  3.14159  3.14159 -0.75000  0.75000
-1

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

Автор:А. Усманов   Ограничение времени:1 сек
Ввод / вывод:интерактивный   Ограничение памяти:256 Мб

Условие

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

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

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

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

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

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

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

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

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

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

Язык C++ Pascal Java Python
Код cout.flush() flush(output) System.out.flush() stdout.flush()

Ограничения

1 ≤ N, X ≤ 255

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

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

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

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

Стандартный вход Стандартный выход
1

>

<

>

<

=
R 4

R 4

L 6

R 4

L 1

! 5
2

<

>
R 14

L 2

! 13

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

Автор:И. Блинов, А. Жихарева   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 100000, 0 ≤ M ≤ 500000, 1 ≤ ai, bi ≤ N

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3
1 2
2 3
3 1
Yes
1 2 
3 1
2
5 4
1 2
2 3
3 4
4 5
Yes
4 5
3 4
2 3
1 2
3
4 2
1 2
3 4
No
4
2 0
No
5
4 6
1 2
1 3
1 4
2 3
2 4
3 4
Yes
3 4
2 3
1 2
6
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. Геройская армия

Автор:И. Блинов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Вторая строка содержит 14 чисел pi, мощность одного существа видов 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 пар, tij qij — вид существа и количество существ этого вида у i-го героя.

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

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

Ограничения

1 ≤ N ≤ 50

0 ≤ M ≤ 5000

0 ≤ pi, ci, qi ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
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
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
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. Несоседние буквы

Автор:М. Спорышев, А. Щуров   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

0 < |S| ≤ 106

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

Входной файл (input.txt) Выходной файл (output.txt)
1
abc
-1
2
abbcd
cadbb

0.707s 0.018s 33