Высшая проба - 2021. Заключительный этап
Statement is not available in English language
A. Круглый Граф
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У графа Михаила есть $$$n$$$ усадеб расположенных по кругу. Он хочет построить несколько подземных переходов между усадьбами, чтобы перемещаться между ними быстрее. Вы можете выбрать какое-то число $$$k$$$, такое, что для каждой усадьбы она будет соединена с соседними $$$k$$$ усадьбами слева и $$$k$$$ усадьбами справа. Какое же минимальное $$$k$$$ вы должны выбрать, чтобы кратчайшее расстояние между любыми двумя усадьбами было не больше $$$d$$$? Расстояние между двумя усадьбами измерятеся в количестве переходов, которые нужно сделать, чтобы добраться из одной усадьбы в другую.

Входные данные

Первая строка содержит одно целое число $$$t$$$ $$$(1 \le t \le 10)$$$ — число наборов входных данных.

Для каждого набора входных данных на новой строке вводится два целых числа $$$n$$$ и $$$d$$$ $$$(3 \le n \le 10^{12}, 1 \le d \le 10^{12})$$$.

Выходные данные

Для каждого набора входных данных выведите одно число — минимальное $$$k$$$ удовлетворяющее условию. Числа разделяйте переводами строк или пробелами.

Система оценки

Решения, корректно работающие при $$$n, d \le 10^4$$$ получат не менее 25% баллов.

Решения, корректно работающие при $$$n, d \le 10^9$$$ получат не менее 70% баллов.

Пример
Входные данные
2
6 2
3 1
Выходные данные
2
1
Примечание

В первом наборе входных данных если мы соединим каждую усадьбу с каждым из соседей (т.е. если $$$k$$$ = 1), то для попадания в противоположную усадьбу нужно будет совершить 3 перехода (см. рисунок)

Если соединить каждую усадьбу с двумя соседями ($$$k$$$ = 2) будет ситуация как на рисунке и потребуется не больше двух переходов для попадания из любой усадьбы в любую.

Во втором наборе данных мы просто соединяем все усадьбы ($$$k$$$ = 1).

Statement is not available in English language
B. Игра в спички
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даша и Света играют со спичками, составляя из них разные фигурки. Всего у девочек есть ровно $$$k$$$ спичек, и сегодня их задача — собирать прямоугольные сетки. Фигура называется прямоугольной сеткой размера $$$n×m$$$, если спички представляют собой прямоугольник размера n×m расчерченный на единичные квадраты, где каждый отрезок разъединяющий квадратики изображается спичкой (для лучшего понимания рассмотрите примеры). А вот формы у прямоугольников бывают разные. Соответственно задача Даши — собрать прямоугольник минимальной площади из ровно $$$k$$$ спичек, а Светы — собрать прямоугольник максимальной площади из ровно $$$k$$$ спичек. Помогите девочкам найти размеры искомых прямоугольников.

Входные данные

В первой строке вводится целое число $$$t$$$ $$$(1 \le t \le 10)$$$ — число наборов входных данных. Далее каждый набор описывается одним числом $$$k$$$ $$$(1 \le k \le 10^9)$$$ — числом спичек, которые есть у девочек.

Выходные данные

Для каждого набора входных данных выведите минимальную и максимальную возможную площадь занимаемую прямоугольной сеткой из ровно $$$k$$$ спичек. Если же прямоугольник собрать невозможно, вместо обоих чисел необходимо вывести одно число «-1».

Система оценки

Решения работающие корректно при $$$k \le 1000$$$ получат не менее 30% баллов.

Решения работающие корректно при $$$k \le 10^6$$$ получат не менее 60% баллов.

Пример
Входные данные
4
4
7
22
3
Выходные данные
1 1
2 2
7 8
-1
Примечание

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

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

В третьем наборе данных возможны варианты 1 × 7, 7 × 1, 2 × 4 и 4 × 2, первые два имеют площадь 7, следующие два имеют площадь 8.

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

Statement is not available in English language
C. Битовая сортировка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Девочке Софии очень нравится бинарная запись числа. Однажды вечером она выписывала случайные числа. По счастливой случайности все эти числа были $$$k$$$-битными, то есть для любого числа $$$a_i$$$, которое София написала, выполняется $$$0 \le a_i \lt 2^k$$$. После этого ее заинтересовал вопрос: если она может поменять значение одного бита в одном из чисел на противоположное, то за какое минимальное количество подобных действий она сможет отсортировать свой список по неубыванию?

Входные данные

В первой строке вводится число $$$t$$$ $$$(1 \le t \le 100)$$$ — количество наборов входных данных. Для каждого набора входных данных вводятся числа $$$n$$$ и $$$k$$$ $$$(1 \le n \le 100, 1 \le k \le 30)$$$. В следующих $$$n$$$ строках вводятся $$$k$$$-битные целые числа $$$a_i$$$, которые написала София $$$(0 \le a_i \lt 2^k)$$$. Числа записаны в двоичной системе счисления (от старших разрядов к младшим) с ровно $$$k$$$ битами.

Гарантируется, что сумма n по всем наборам входных данных не превосходит 100.

Выходные данные

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

Система оценки

Решения, работающие корректно при $$$n \le 2$$$ получат не менее 10% баллов.

Решения, работающие корректно при $$$n \le 10$$$ получат не менее 40% баллов.

Решения, работающие корректно при $$$k \le 10$$$ получат не менее 40% баллов.

Пример
Входные данные
4
3 3
000
101
010
3 3
000
111
010
3 3
100
111
010
1 1
0
Выходные данные
1
2
2
0
Примечание

В первом наборе данных достаточно изменить первый бит во втором числе. Тогда получится последовательность 000, 001, 010, что в десятичной системе будет 0,1,2.

Во втором наборе данных можно изменить первые два бита второго числа. Тогда получится последовательность 000, 001, 010, что в десятичной системе будет 0, 1, 2.

Во третьем наборе данных можно изменить первый и последний бит последнего числа. Тогда получится последовательность 100, 111, 111, что в десятичной системе будет 4, 7, 7.

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

Statement is not available in English language
D. Run, Pancake, Run
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Каждая комната содержит тарелку, в которой находится ровно $$$k$$$ блинов. Каждый переход содержит тарелку, в которой находится ровно 2 блина.

Пробежка Тимура выглядит следующим образом:

  1. Тимур стартует в любой из комнат и ест в ней 1 блин. Переходит к шагу 2.
  2. Тимур, находясь в комнате $$$v$$$, выбирает некоторую комнату $$$u$$$, такую, что:
    • Переход между $$$v$$$ и $$$u$$$ существует и содержит хотя бы 1 блин.
    • Комната $$$u$$$ содержит хотя бы 1 блин.
    Если такой комнаты не существует, Тимур расстраивается и немедленно прекращает пробежку. Иначе он переходит к шагу 3.
  3. Тимур перебегает из $$$v$$$ в $$$u$$$, съедая по одному блину в переходе между ними и в комнате $$$u$$$, после чего возвращается к шагу 2.

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

Входные данные

Первая строка теста содержит одно целое число $$$t$$$ $$$(t \le 100)$$$ — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных, разделенные пустой строкой.

Первая строка набора тестовых данных содержит два целых числа $$$n$$$, $$$k$$$ $$$(1 \le n \le 10^5, 1 \le k \le 10^9)$$$.

Следующая $$$n − 1$$$ строка набора тестовых данных содержит два целых числа $$$v$$$, $$$u$$$ $$$(1 \le v, u \le n, u \neq v)$$$ — описание переходов. Гарантируется, что переходы задают дерево.

Гарантируется, что сумма $$$n$$$ в тестовых наборах не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора тестовых данных выведите в отдельной строке одно целое число — ответ на него.

Система оценки
ГруппаБаллыДоп. ограниченияКомментарий
sum$$$_n$$$$$$k$$$
$$$0$$$0——Тесты из условия
$$$1$$$2$$$n \le 1$$$ $$$000$$$$$$k=1$$$
$$$2$$$2—$$$k=1$$$
$$$3$$$3$$$n \le 300$$$$$$k=2$$$
$$$4$$$4$$$n \le 20$$$—
$$$5$$$4$$$n \le 1$$$ $$$000$$$—
$$$6$$$5——

Тесты к этой задаче состоят из 6 групп. Каждый тест в группе оценивается в 1 балл.

Примеры
Входные данные
3
7 1
1 2
1 3
2 4
2 5
3 6
3 7

4 2
1 2
1 3
1 4

2 10
1 2
Выходные данные
40
40
20
Входные данные
1
12 2
7 8
4 5
7 11
8 10
6 7
4 3
9 7
3 2
4 6
1 2
12 11
Выходные данные
160

Statement is not available in English language
E. Метро
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
768 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В столице Берляндии построили первую линию метро. Линия содержит $$$n + 1$$$ станцию и $$$n$$$ перегонов между ними, $$$i$$$-й перегон соединяет станции с номерами $$$i$$$ и $$$i + 1$$$ и стоимость проезда по нему равна $$$c_i$$$.

Перед полным открытием метро правительство Берляднии планирует сделать m тестовых запусков метро. В $$$i$$$-м запуске будут открыты станции, номера которых не меньше $$$l_i$$$ и не больше $$$r_i$$$, а также все перегоны между этими станциями. В каждом тестовом запуске метро для каждой пары станций с номерами $$$a$$$ и $$$b$$$, таких что $$$a \lt b$$$, будет пущен поезд из станции a в станцию $$$b$$$, с остановками на всех промежуточных станциях. Например если всего в метро 5 станций и во время тестового запуска будет открыты станции между 2 и 4, то будет пущен поезд со станции 2 на станцию 3, со станции 3 на станцию 4 и со станции 2 на станцию 4 с промежуточной остановкой на станции 3.

Чтобы показать доступность метро, правительство Берляндии для каждого тестового запуска выбирает число $$$k_i$$$ и считает $$$k_i$$$-й минимальный по стоимости проезда перегон среди открытых перегонов в $$$i$$$-й день, при этом каждый перегон учитывается столько раз, сколько поездов по нему проезжает. Другими словами правительство Берляднии хочет выписать стоимость проезда по каждому перегону столько раз, сколько поездов по нему проехало, после чего отсортировать полученный массив по возрастанию и найти в нём $$$k_i$$$-е число. Помогите правительству Берляндии найти такой перегон для каждого из тестовых запусков.

Входные данные

В первой строке вводятся два целых числа $$$n$$$ и $$$m$$$ $$$(1 \le n, m \le 300$$$ $$$000)$$$ — число перегонов и число тестовых запусков метро.

В следующей строке вводятся $$$n$$$ чисел $$$c_1, c_2, c_3, \dotsc , c_n$$$ $$$(1 \le c_i \le 500$$$ $$$000)$$$ — стоимости проезда по перегонам метро.

Следующие $$$m$$$ строк описывают тестовые запуски. В $$$i$$$-й строке вводятся три целых числа $$$l_i$$$, $$$r_i$$$ и $$$k_i$$$ $$$(1 \le l_i \lt r_i \le n + 1, 1 \le k_i \le \frac{1}{6}(r_i - l_i)(r_i - l_i + 1)(r_i - l_i + 2))$$$ — первая открытая станция, последняя открытая станция и какой по стоимости перегон надо найти.

Выходные данные

Для каждого тестового запуска в отдельной строке выведите стоимость $$$k_i$$$-го минимального по стоимости перегона среди всех открытых перегонов в $$$i$$$-й день, при этом учитывая каждый перегон столько раз, сколько поездов по нему проезжают в $$$i$$$-й тестовый запуск.

Система оценки

В задаче 21 тестов, каждый тест кроме первого независимо оценивается в 1 балл. Тесты можно разделить на 10 групп:

ГруппаМакс. баллДополнительные ограниченияКомментарий
$$$n$$$$$$m$$$$$$c_i$$$$$$k_i$$$
$$$0$$$0————Тесты из условия.
$$$1$$$1$$$n \le 10$$$$$$m \le 100$$$$$$c_i \le 10$$$—
$$$2$$$2$$$n \le 100$$$$$$m \le 100$$$$$$c_i \le 100$$$—
$$$3$$$2$$$n \le 100$$$—$$$c_i \le 100$$$—
$$$4$$$2$$$n \le 500$$$$$$m \le 500$$$$$$c_i \le 500$$$—
$$$5$$$2$$$n \le 10$$$ $$$000$$$$$$m \le 10$$$ $$$000$$$$$$c_i \le 10$$$ $$$000$$$—
$$$6$$$2$$$n \le 100$$$ $$$000$$$$$$m \le 100$$$ $$$000$$$$$$c_i \le 30$$$—
$$$7$$$3$$$n \le 100$$$ $$$000$$$$$$m \le 100$$$ $$$000$$$——
$$$8$$$2——$$$c_i \le 2$$$—
$$$9$$$2——$$$c_i \le 500$$$$$$k_i \le 500$$$
$$$10$$$2————
Пример
Входные данные
5 6
1 2 3 2 3
1 3 2
1 4 7
3 6 4
1 6 35
2 5 7
2 6 10
Выходные данные
1
2
2
3
3
2