Это интерактивная задача.
Вам дано дерево — связный неориентированный граф без циклов. В нём загадали одну из вершин. Вы можете задавать вопросы интерактору: за один вопрос вы можете выбрать ребро и узнать, какой из двух концов ребра находится ближе к загаданной вершине, то есть, до какого из двух концов меньше кратчайшее расстояние от загаданной вершины. Вам требуется определить загаданную вершину за минимальное для данного дерева число запросов в худшем случае.
Обратите внимание, что загаданная вершина может быть не фиксирована интерактором заранее: в зависимости от ваших запросов он может менять её на любую другую, с условием, что это не противоречит ответам на предыдущие запросы.
В первой строке входных данных содержится целое число $$$n$$$ ($$$2 \le n \le 100$$$) — количество вершин в дереве.
В каждой из следующих $$$n-1$$$ строк записаны два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$), обозначающих ребро между вершинами $$$u$$$ и $$$v$$$. Гарантируется, что данные ребра образуют дерево.
После считывания выходных данных вы можете отправлять интерактору запросы двух типов:
После каждого вопроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Idleness Limit Exceeded или Превышено реальное время работы. Для сброса буфера вы можете использовать:
В случае, если вы сделаете большее число запросов, чем может быть необходимо для данного дерева в худшем случае, вы получите вердикт Неправильный ответ.
5 1 2 2 3 3 4 4 5 3 2 1
? 3 4 ? 2 3 ? 1 2 ! 1
5 2 1 3 1 4 1 5 1 1 1 4
? 1 2 ? 1 3 ? 1 4 ! 4
В одной очень известной олимпиаде участвуют более ста человек. Олимпиада состоит из двух этапов: отборочного и заключительного. В заключительный этап проходят хотя бы сто участников. Отборочный же этап состоит из двух туров.
В каждом туре участников упорядочивают по невозрастанию баллов. В случае, если два участника набрали одинаковый балл, они упорядочиваются по номеру паспорта. В соответствии с законодательством номера паспортов всех участников различны.
В первом туре участник на сотом месте набрал $$$a$$$ баллов, при этом все участники первого тура, занявшие места от первого до сотого включительно, набрали не менее $$$b$$$ баллов во втором туре.
Во втором туре участник на сотом месте набрал $$$c$$$ баллов, при этом все участники второго тура, занявшие места от первого до сотого включительно, набрали не менее $$$d$$$ баллов в первом туре.
Упорядочим всех участников по невозрастанию суммы их баллов за два тура. При равенстве результатов упорядочим участников по номеру паспорта. Тогда проходной балл для попадания в заключительный этап — это сумма баллов за оба тура у участника на сотом месте.
Помогите жюри узнать, каким может быть минимальный проходной балл на заключительный этап.
В единственной строке содержатся четыре целых числа $$$a$$$, $$$b$$$, $$$c$$$ и $$$d$$$ ($$$0 \le a,\,b,\,c,\,d \le 100;\ d \leq a;\ b \leq c$$$). Можно показать, что для любых входных данных, удовлетворяющих ограничениям из условия, существует хотя бы один корректный вариант проведения олимпиады.
Выведите одно целое число — ответ на задачу.
1 2 2 1
3
4 8 9 2
12
В первом примере на олимпиаду могут отбираться сто один человек с баллами $$$1$$$ и $$$2$$$ за первый и второй тур, соответственно. Сумма баллов у сотого участника будет равна $$$3$$$.
Во втором примере на олимпиаду могло отбираться пятьдесят человек с баллами $$$5$$$ и $$$10$$$, пятьдесят человек с баллами $$$4$$$ и $$$8$$$ и пятьдесят человек с баллами $$$2$$$ и $$$9$$$, соответственно. Сумма баллов у сотого участника будет равна $$$12$$$.
Вы собираетесь пойти в поход. Для этого вам нужно разложить всё снаряжение по нескольким рюкзакам. У вас есть неограниченное количество рюкзаков вместительностью $$$s$$$ литров каждый.
Всем известно, что когда идёшь в поход, вещи каждого типа нужно брать в нескольких экземплярах, чтобы если одна промокнет, была запасная. Разумеется, разные вещи одного типа нужно класть в разные рюкзаки.
Вы решили взять в поход вещи $$$n$$$ типов, причём вещей типа $$$i$$$ вы решили взять $$$k_i$$$ штук. Каждая вещь имеет свой объем — $$$j$$$-я вещь типа $$$i$$$ имеет объём $$$w_{i, j}$$$. Вы хотите, используя минимальное число рюкзаков, разложить все имеющиеся вещи по ним так, чтобы суммарный объем вещей в каждом рюкзаке не превышал $$$s$$$, а также чтобы ни в одном из рюкзаков не оказалось двух вещей одного типа. Определите минимальное количество рюкзаков, которое вам понадобится, чтобы пойти в поход.
В первой строке заданы два целых числа $$$n$$$ и $$$s$$$ ($$$1 \le n \le 23$$$, $$$1 \le s \le 10^{16}$$$) — количество типов предметов и вместительность каждого из рюкзаков.
В следующих $$$n$$$ строках даны описания вещей. В $$$i$$$-й строке содержится описание вещей $$$i$$$-го типа. Описание начинается с одного целого числа $$$k_i$$$ ($$$1 \leq k_i \leq 23$$$) — количества вещей типа $$$i$$$. Затем следуют $$$k_i$$$ целых чисел $$$w_{i, j}$$$ ($$$1 \le w_{i, j} \le s$$$) — объёмы вещей $$$i$$$-го типа.
Суммарное количество вещей не превышает $$$23$$$.
Выведите минимальное количество рюкзаков, которое необходимо, чтобы разместить все вещи по описанным выше правилам.
3 70 3 10 30 40 2 20 60 1 50
4
Рассмотрим пример из условия. В нём есть вещи трёх типов: наверняка это были укулеле, бутылки с водой и гири.
В первый рюкзак можно положить укулеле объёмом 40 литров и бутылку с водой объёмом 20 литров. Во второй рюкзак можно положить укулеле объёмом 10 литров и бутылку с водой объёмом 60 литров. В третий рюкзак можно положить укулеле объёмом 30 литров. В четвёртом рюкзаке будет лежать гиря объёмом 50 литров. Можно показать, что разложить нужные вещи по трём рюкзакам не получится.
Oleg's favourite subjects are History and Math, and his favourite branch of mathematics is division. To improve his division skills, Oleg came up with two integers $$$p$$$ and $$$q$$$ and decided to find the greatest number $$$x$$$ that divides $$$p$$$, but is not divisible by $$$q$$$. Oleg is really good at division and managed to find the answer quickly, how about you?
The first line contains an integer $$$p$$$ ($$$1 \le p \le 10^{100}$$$). The second line contains an integer $$$q$$$ ($$$2 \le q \le 10^{12}$$$). One can show that there is always at least one value of $$$x$$$ satisfying the divisibility conditions for the given constraints.
Output one integer: the greatest number $$$x$$$ that divides $$$p$$$ and is not divisible by $$$q$$$.
10 4
10
12 6
4
179 822
179
In the first example $$$10$$$ is the answer, since it is the maximal divisor of $$$10$$$ and it is not divisible by $$$4$$$.
In the second example $$$12$$$ is not a valid candidate, since $$$12$$$ is divisible by $$$6$$$, and neither is $$$6$$$: it is also divisible by $$$6$$$. The next available divisor is $$$4$$$, which is the answer, since $$$4$$$ is not divisible by $$$6$$$.
В далекой стране Байтландии сегодня проходит парад. Военные машины уже проехали по городу, самолёты уже пролетели, остался лишь марш солдат, который вам и предстоит организовать в кратчайшие сроки.
Всего в марше должны были участвовать $$$n$$$ отрядов солдат, по $$$m$$$ солдат в каждом. К сожалению, собираться большим числом людей в наши времена крайне сложно, и вы решили, что хотите выбрать из $$$n$$$ отрядов по одному представителю и пройти одной большой шеренгой длины $$$n$$$. Выбранные солдаты будут расположены в шеренге в порядке возрастания номеров их отрядов.
Ваше начальство хочет, чтобы строй был максимально ровным из возможных. Неровность шеренги определяется максимальным модулем разности роста соседних солдат.
Время поджимает — выходить уже через 5 часов! Определите, какой минимальной неровности шеренги можно добиться при таких условиях.
В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le nm \le 10^6$$$) — количество отрядов и число солдат в каждом из них.
В следующих $$$n$$$ строках находится по $$$m$$$ целых чисел $$$a_{i, j}$$$ ($$$10^6 \leq a_{i, j} \leq 2 \cdot 10^6$$$) — высота в микрометрах $$$j$$$-го солдата $$$i$$$-го отряда.
Выведите одно число — минимальную возможную неровность шеренги в микрометрах.
3 4 1830000 1790000 1810000 1820000 1730000 1690000 1750000 1760000 1910000 1850000 1800000 1710000
40000
В тесте из условия одним из оптимальных вариантов будет шеренга из солдат с ростами: 179 см, 176 см, 180 см. Модуль разности роста первого и второго солдатов составляет 3 см, а второго и третьего — 4. Таким образом, неровность шеренги равна 4 см или 40000 микрометров.
2 2 1 1 2 1 1 2 1 2 2 3 3
Yes 1 0 1 1 0 1 0 0 No
2 4 1 1 1 1 4 1 1 1 1 3 2 1 1 3 2 1 1
Yes 1 0 1 1 2 1 2 2 1 2 1 1 0 1 0 0 Yes 0 -2 2 -2 2 -1 1 -1 1 0 0 0
2 4 1 4 1 2 4 3 4 5 12 4 1 2 3 6 2 1 3
Yes 2 0 2 3 3 3 3 7 4 7 4 12 0 12 0 0 No
6 8 3 1 1 2 2 3 3 1 3 1 5 1 6 2 5 2 6 3 4 3 5 5 6
2
4 3 3 1 1 2 2 1 2 2 3 3 4
3
4 4 2 1 1 1 2 1 2 2 3 3 1 1 4
0
5 5 2 1 2 1 2 1 1 2 2 3 3 4 4 5 5 1
0
После тяжёлого рабочего дня Алексей решил расслабиться за просмотром телевизора. Всего есть $$$n$$$ телеканалов, на $$$i$$$-м телеканале показывают интересную для Алексея передачу в отрезок времени $$$[l_i, r_i]$$$.
Так как жизнь Алексея расписана по минутам, то он смотрит телевизор по определенному алгоритму. Пусть в текущий момент Алексей смотрит телеканал $$$x$$$ в момент времени $$$t$$$. Тогда:
Алексей пока не определился, в какой момент и с какого телеканала начать просмотр. У него есть $$$m$$$ вариантов, $$$i$$$-й вариант предполагает начало просмотра телевизора с телеканала $$$x_i$$$ в момент времени $$$t_i$$$. Для каждого из вариантов определите время, которое Алексей проведет за просмотром интересных передач.
В первой строке содержится целое число $$$n$$$ ($$$1 \le n \le 300\,000$$$) — количество телеканалов.
Следующие $$$n$$$ строк содержат описания телеканалов: $$$i$$$-я строка содержит два числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \lt r_i \le 10^9$$$) — отрезок времени, на протяжении которого на $$$i$$$-м телеканале идёт интересная передача.
В следующей строке задано целое число $$$m$$$ ($$$1 \le m \le 300\,000$$$) — количество вариантов просмотра.
Следующие $$$m$$$ строк содержат описания вариантов просмотра, в $$$i$$$-й строке содержатся два целых числа $$$x_i$$$ и $$$t_i$$$ ($$$1 \le x_i \le n; 1 \le t_i \le 10^9$$$) — номер телеканала и момент времени, соответственно.
Для $$$i$$$-го варианта просмотра выведите одно целое число — суммарное время, которое Алексей будет смотреть интересные передачи, если начнет просмотр с телеканала $$$x_i$$$ в момент времени $$$t_i$$$.
3 1 3 2 4 7 10 4 1 2 2 5 1 7 3 10
2 0 3 0
Рассмотрим тест из условия.
Если Алексей начнёт просмотр с первого телеканала в момент времени $$$2$$$, то он будет смотреть на нём интересную передачу в течение одной минуты до момента времени $$$3$$$, затем переключится на второй канал, на котором будет смотреть интересную передачу в течение одной минуты до момента времени $$$4$$$. В момент времени $$$4$$$ Алексей переключится на третий канал, по которому в этот момент не идёт интересная передача, поэтому в этот момент он закончит просмотр телевизора.
Во втором варианте просмотра, в момент времени $$$5$$$ интересная передача не идёт ни по одному из каналов, поэтому Алексей сразу завершит просмотр.
В третьем варианте просмотра Алексей начнёт просмотр с первого канала в момент времени $$$7$$$, так что он переключится сразу на второй, а потом и сразу на третий канал, после чего будет смотреть на нём интересную передачу в течение трёх минут до момента времени $$$10$$$, после чего завершит просмотр телевизора.
An integer $$$ n $$$ and an array $$$ a $$$ of length $$$ 2n $$$ are given. Consider splitting the array $$$ a $$$ into two subsequences $$$ p $$$ and $$$ q $$$ of length $$$ n $$$. We sort $$$ p $$$ non-decreasing, and $$$ q $$$ non-increasing, and we get the sequences $$$ x $$$ and $$$ y $$$, respectively. Then we call the cost of the partition $$$ f(p, q) = \sum_{i = 1}^n |x_i - y_i|$$$.
Calculate the sum of $$$f(p, q)$$$ over all correct partitions of $$$ a $$$. Since this number can be truly huge, you need to calculate it modulo $$$998244353$$$. Ogneslav awaits his fiery deeds, so he asks to solve this problem for him.
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 150\,000$$$).
The second line contains $$$ 2n $$$ integer numbers $$$a_1, a_2, \ldots, a_{2n}$$$ ($$$1 \leq a_i \leq 10^9$$$) — array elements.
Print one integer number — the answer to the problem modulo $$$998244353$$$.
1 1 4
6
2 2 1 2 1
12
3 2 2 2 2 2 2
0
Two partitions of an array are considered different if the sets of indices of elements included in the subsequence $$$ p $$$ differ.
In the first example, there are two correct partitions of the array $$$ a $$$:
In the second example, there are six valid partitions of the $$$ a $$$ array: