У графа Михаила есть $$$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).

Даша и Света играют со спичками, составляя из них разные фигурки. Всего у девочек есть ровно $$$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 спичек невозможно собрать никакой прямоугольник

Девочке Софии очень нравится бинарная запись числа. Однажды вечером она выписывала случайные числа. По счастливой случайности все эти числа были $$$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.
В четвертом примере ничего менять не надо, так как последовательность уже неубывающая.
Тимур решил заняться пробежками по общежитию. Он мотивирует себя блинами. Общежитие состоит из n комнат, некоторые пары из которых соединены переходами длиной 10 метров. Общежитие является деревом, то есть для каждой пары комнат существует ровно один путь их соединяющий.
Каждая комната содержит тарелку, в которой находится ровно $$$k$$$ блинов. Каждый переход содержит тарелку, в которой находится ровно 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
В столице Берляндии построили первую линию метро. Линия содержит $$$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