У Монокарпа есть $$$n$$$ карточек, на которых записано ровно по одному целому числу от $$$1$$$ до $$$n$$$, причем каждое из целых чисел от $$$1$$$ до $$$n$$$ записано ровно на одной карточке.
Монокарп выложил все карточки в ряд по следующему правилу: сначала он выложил все карточки с четными числами в порядке возрастания, а затем все карточки с нечетными числами в порядке убывания.
Например, если $$$n = 7$$$, то порядок чисел на выложенных карточках следующий: $$$[2, 4, 6, 7, 5, 3, 1]$$$.
Перед вами стоит задача определить, какое число записано на карточке, которая была выложена $$$k$$$-й по счету (то есть определить число, которое записано на $$$k$$$-й карточке слева).
В первой строке следует целое число $$$n$$$ ($$$2 \le n \le 1\,000\,000$$$) — количество карточек.
Во второй строке следует целое число $$$k$$$ ($$$1 \le k \le n$$$) — номер карточки слева, для которой нужно определить записанное на ней число.
Выведите число, которое записано на карточке, которая была выложена $$$k$$$-й по счету.
53
5
128
9
41
2
В первом примере порядок чисел на выложенных карточках следующий: $$$[2, 4, 5, 3, 1]$$$. На третьей слева карточке записано число $$$5$$$.
Во втором примере порядок чисел на выложенных карточках следующий: $$$[2, 4, 6, 8, 10, 12, 11, 9, 7, 5, 3, 1]$$$. На восьмой слева карточке записано число $$$9$$$.
В третьем примере порядок чисел на выложенных карточках следующий: $$$[2, 4, 3, 1]$$$. На первой слева карточке записано число $$$2$$$.
Перестановкой длины $$$n$$$ называется массив из $$$n$$$ элементов, где каждое целое число от $$$1$$$ до $$$n$$$ встречается ровно один раз.
Была некоторая перестановка $$$p$$$ длины $$$n$$$. По этой перестановке построили два массива длины $$$n$$$: $$$[a_1, a_2, \dots, a_n]$$$ и $$$[b_1, b-2, \dots, b_n]$$$, где $$$a_i$$$ — расстояние от $$$i$$$-й позиции в перестановке до позиции максимального элемента, а $$$b_i$$$ — расстояние от $$$i$$$-й позиции в перестановке до позиции минимального элемента.
Например, по перестановке $$$p = [3, 2, 5, 1, 4]$$$ получились бы следующие массивы: $$$a = [2, 1, 0, 1, 2]$$$ и $$$b = [3, 2, 1, 0, 1]$$$.
После построения массивов $$$a$$$ и $$$b$$$ все числа в них сложили и получили число $$$m$$$. Ваша задача — по заданным $$$n$$$ и $$$m$$$ восстановить любую подходящую перестановку $$$p$$$.
В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 2000$$$) — количество наборов входных данных.
Каждый набор входных данных состоит из одной строки, содержащей два целых числа $$$n$$$ и $$$m$$$ ($$$3 \le n \le 6000$$$; $$$0 \le m \le n \cdot (n-1)$$$).
Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превосходит $$$6000$$$.
На каждый набор входных данных выведите ответ следующим образом:
- если подходящей перестановки $$$p$$$ длины $$$n$$$, из которой в ходе описанного процесса было бы получено заданное число $$$m$$$, не существует, выведите $$$0$$$;
- иначе выведите $$$n$$$ различных целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$) — искомую перестановку. Если подходящих перестановок несколько, вы можете вывести любую из них.
35 135 123 6
3 2 5 1 4 0 1 2 3
Дан ориентированный граф, состоящий из $$$n$$$ вершин и $$$m$$$ ребер. В этом графе могут быть кратные ребра и петли.
Вы можете в некоторых вершинах построить порталы; после этого из любой вершины, в которой есть портал, можно будет переместиться в любую другую вершину, в которой есть портал. Кроме того, можно перемещаться по ребрам заданного графа.
Ваша задача — построить минимальное количество порталов так, чтобы из каждой вершины можно было добраться до каждой другой вершины.
В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le m \le 2 \cdot 10^5$$$) — количество вершин и ребер, соответственно.
Следующие $$$m$$$ строк содержат ориентированные ребра: ребро $$$i$$$ представлено в виде пары вершин $$$v_i$$$, $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$). Кратные ребра и петли допустимы для заданного графа.
Выведите одно целое число — минимальное количество порталов.
4 5
4 3
1 2
3 1
1 2
2 4
0
9 10
1 4
1 1
3 1
5 2
4 1
6 4
2 7
7 5
4 9
1 7
5
В первом примере из условия все вершины и так достижимы друг из друга, поэтому ни один портал не нужен.
Во втором примере из условия можно построить порталы в вершинах $$$3$$$, $$$5$$$, $$$6$$$, $$$8$$$ и $$$9$$$.
Монокарп недавно изучил двоичную систему счисления. Теперь он умеет переводить целые положительные числа из десятичной системы счисления в двоичную. После перевода он записывает число в двоичной системе счисления, начиная со старшего значимого разряда, равного $$$1$$$, то есть записывает числа без лидирующих нулей.
Монокарпу стало интересно, сколько целых десятичных чисел в промежутке от $$$a$$$ до $$$b$$$ включительно в своей двоичной записи имеют ровно $$$k$$$ разрядов, равных $$$1$$$.
Перед вами стоит задача помочь Монокарпу ответить на этот вопрос.
В первой строке следует одно целое число $$$t$$$ ($$$1 \le t \le 1\,000$$$) — количество наборов входных данных.
В единственной строке каждого набора входных данных следуют три целых числа $$$a$$$, $$$b$$$ и $$$k$$$ ($$$1 \le a \le b \le 10^{9}$$$, $$$1 \le k \le 30$$$) — левая и правая границы промежутка, а также количество разрядов, которые должны быть равны $$$1$$$ в двоичной записи числа.
Для каждого набора входных данных выведите в отдельную строку одно целое число — количество целых чисел в промежутке от $$$a$$$ до $$$b$$$ включительно, которые в своей двоичной записи имеют ровно $$$k$$$ разрядов, равных $$$1$$$.
34 15 263 63 61 1000000000 21
5110722629
В первом наборе входных данных в промежутке $$$[4, 15]$$$ существует $$$5$$$ чисел, в двоичной записи которых встречается ровно $$$2$$$ разряда, равных $$$1$$$: $$$5_{10} = 101_{2}$$$, $$$6_{10} = 110_{2}$$$, $$$9_{10} = 1001_{2}$$$, $$$10_{10} = 1010_2$$$ и $$$12_{10} = 1100_{2}$$$.
Во втором наборе входных данных в промежутке $$$[63, 63]$$$ есть ровно одно целое число $$$63_{10} = 111111_{2}$$$, в записи которого $$$6$$$ разрядов, равных $$$1$$$, поэтому ответ на этот набор входных данных равен $$$1$$$.
У Монокарпа есть массив $$$a$$$, состоящий из $$$n$$$ целых элементов, причем $$$i$$$-й элемент массива равен $$$a_i$$$.
Монокарп хочет, чтобы разность между максимальным и минимальным элементами в его массиве не превышала целого числа $$$d$$$.
Для этого он может ровно один раз удалить некоторое (возможно, нулевое) количество подряд идущих элементов своего массива. После этого неудаленные элементы образуют новый массив, причем относительный порядок оставшихся элементов не меняется.
Монокарпу очень нравится его массив, поэтому он хочет удалить как можно меньше подряд идущих элементов из своего массива так, чтобы разность между максимальным и минимальным элементами в его массиве после удаления элементов не превышала целого числа $$$d$$$.
Перед вами стоит задача помочь Монокарпу и определить минимальное количество подряд идущих элементов, которые необходимо удалить из его массива.
В первой строке следуют два целых числа $$$n$$$ и $$$d$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le d \le 10^{9}$$$) — количество элементов в массиве Монокарпа и максимально допустимая разность между максимальным и минимальным элементами массива.
Во второй строке следует последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$), причем $$$i$$$-й элемент последовательности равен $$$i$$$-му элементу массива Монокарпа.
Выведите минимальное количество подряд идущих элементов массива Монокарпа, которые нужно удалить таким образом, чтобы разность между максимальным и минимальным элементами в массиве Монокарпа после удаления элементов не превышала целого числа $$$d$$$.
6 33 3 1 8 5 4
2
7 1015 12 18 13 12 11 16
0
В первом примере нужно удалить два подряд идущих элемента в позициях $$$4$$$ и $$$5$$$. После этого массив станет равным $$$[3, 3, 1, 4]$$$. Разность между максимальным и минимальным элементами в этом массиве равна $$$4 - 1 = 3$$$. Так как $$$d = 3$$$, этот массив является подходящим.
Во втором примере не нужно удалять ни одного элемента, так как разность между максимальным и минимальным элементами в этом массиве равна $$$18 - 11 = 7$$$. Так как $$$d = 10$$$, этот массив является подходящим.
У Монокарпа есть последовательность $$$a$$$, состоящая из $$$n$$$ целых чисел, причем $$$i$$$-й элемент последовательности равен $$$a_i$$$.
Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ Монокарп хочет узнать минимальное количество элементов, которые нужно удалить из его последовательности, чтобы элемент $$$a_i$$$ (то есть элемент, который находился в позиции $$$i$$$ до удаления) стал максимальным (или одним из максимальных) среди оставшихся элементов в последовательности.
Вам нужно помочь Монокарпу с этой задачей.
В первой строке следует целое число $$$n$$$ ($$$2 \le n \le 200\,000$$$) — количество элементов в последовательности.
Во второй строке следует последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$), где $$$a_i$$$ равно $$$i$$$-му элементу последовательности Монокарпа.
Выведите $$$n$$$ целых чисел через пробел, причем $$$i$$$-е число должно быть равно минимальному количеству элементов, которые нужно удалить из последовательности, чтобы элемент, который находился в позиции $$$i$$$ до удаления, стал максимальным (или одним из максимальных) среди оставшихся элементов в последовательности.
52 5 1 7 5
3 1 4 0 1
4100 100 100 100
0 0 0 0
115 3 4 5 4 3 2 4 6 5 2
1 7 4 1 4 7 9 4 0 1 9
Рассмотрим подробнее первый пример.
Чтобы первый элемент (число $$$2$$$) стал максимальным в последовательности, нужно удалить три элемента: второй, четвертый и пятый.
Чтобы второй элемент (число $$$5$$$) стал одним из максимальных в последовательности, нужно удалить четвертый элемент.
Чтобы третий элемент (число $$$1$$$) стал максимальным в последовательности, нужно удалить четыре элемента: первый, второй, четвертый и пятый.
Четвертый элемент (число $$$7$$$) изначально максимальный в последовательности, поэтому ничего удалять не нужно.
Чтобы пятый элемент (число $$$5$$$) стал одним из максимальных в последовательности, нужно удалить четвертый элемент.
Есть полоска, разделенная на $$$n$$$ клеток, пронумерованных от $$$1$$$ до $$$n$$$ слева направо. Изначально все клетки являются бесцветными.
Мы проводим $$$(n-1)$$$ операцию; номера операций начинаются с $$$1$$$. В ходе $$$i$$$-й операции мы выбираем любое количество подряд идущих клеток и красим их в цвет $$$i$$$. Если какие-то клетки ранее были покрашены, их цвет меняется на новый.
Раскраской называется последовательность цветов клеток $$$c_1, c_2, \dots, c_n$$$, где $$$c_i$$$ — цвет $$$i$$$-й клетки. Назовем раскраску красивой, если для нее выполняются следующие условия:
- раскраску можно получить путем применения $$$(n-1)$$$ операций, описанных выше;
- ни одна клетка в раскраске не является бесцветной;
- для каждого цвета от $$$1$$$ до $$$n-1$$$ существует хотя бы одна клетка с этим цветом.
Посчитайте количество красивых раскрасок. Две раскраски являются различными, если цвет хотя бы одной клетки в этих раскрасках отличается.
В единственной строке задано одно целое число $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — количество клеток в полоске.
Выведите одно целое число — количество красивых раскрасок, взятое по модулю $$$998244353$$$.
2
1
3
5
5
154
1337
357599079
Для $$$n = 2$$$ существует только одна раскраска: $$$[1, 1]$$$.
Для $$$n = 3$$$ существуют следующие $$$5$$$ раскрасок:
- $$$[1, 2, 2]$$$: можно первой операцией покрасить первую клетку, а второй — две оставшиеся клетки;
- $$$[1, 1, 2]$$$: можно первой операцией покрасить первые две клетки, а второй — оставшуюся клетку;
- $$$[2, 2, 1]$$$: можно первой операцией покрасить третью клетку, а второй — две оставшиеся клетки;
- $$$[2, 1, 1]$$$: можно первой операцией покрасить вторую и третью клетку, а второй — первую клетку;
- $$$[1, 2, 1]$$$: можно первой операцией покрасить всю полоску, а второй — перекрасить центральную клетку.
У Монокарпа есть строка $$$s$$$ длины $$$n$$$, состоящая из строчных букв латинского алфавита.
Он хочет разделить свою строку на части, причем должны выполняться следующие условия:
- в каждой части должно быть ровно две различные буквы, причем все одинаковые буквы в каждой части должны идти подряд;
- каждая часть – это некоторая последовательность подряд идущих букв строки $$$s$$$;
- каждая буква строки $$$s$$$ должна оказаться ровно в одной части.
Перед вами стоит задача определить количество способов разделить строку $$$s$$$ на части таким образом, чтобы выполнялись все описанные условия. Так как ответ может быть достаточно большим, выведите его по модулю $$$1\,000\,000\,007$$$.
В первой строке следует целое число $$$n$$$ ($$$2 \le n \le 200\,000$$$) — количество букв в строке Монокарпа.
Во второй строке следует строка $$$s$$$ длины $$$n$$$, состоящая из строчных букв латинского алфавита.
Выведите количество способов разделить строку $$$s$$$ на части таким образом, чтобы выполнялись все описанные условия. Так как ответ может быть достаточно большим, выведите его по модулю $$$1\,000\,000\,007$$$.
6rbbbrr
2
6vkosph
1
3abc
0
18aaabbbcccbbddaaaba
12
В первом примере есть два способа разделения: [rb, bbrr] и [rbb, brr].
Во втором примере есть один способ разделения: [vk, os, ph].
В третьем примере нет ни одного подходящего способа разделения.
Монокарп подошел к пешеходному переходу через дорогу со светофором.
Монокарп знает, что светофор меняет цвета в следующем порядке: сначала горит красный свет, затем горит желтый свет, затем горит зеленый свет, а затем горит желтый свет. После этого на светофоре загорается красный свет, и описанный порядок повторяется вновь.
Также Монокарп знает, что красный свет всегда горит ровно $$$r$$$ секунд, желтый свет всегда горит ровно $$$y$$$ секунд, а зеленый свет всегда горит ровно $$$g$$$ секунд.
В тот момент, когда Монокарп подошел к светофору, на светофоре загорелся красный свет. Монокарпу стало интересно, что произойдет ровно через $$$n$$$ секунд после того момента, когда он подошел к светофору. Перед вами стоит задача помочь Монокарпу.
Если в момент времени, который настанет ровно через $$$n$$$ секунд, на светофоре не будет изменяться свет, определите свет, который будет гореть на светофоре в этот момент времени.
Если в момент времени, который настанет ровно через $$$n$$$ секунд, на светофоре будет меняться свет, то определите свет, который горел непосредственно до этого момента времени, а также определите свет, который будет гореть непосредственно после этого момента времени.
В первой строке следует одно целое число $$$t$$$ ($$$1 \le t \le 1\,000$$$) — количество наборов входных данных.
В единственной строке каждого набора входных данных следуют четыре целых числа $$$r$$$, $$$y$$$, $$$g$$$ и $$$n$$$ ($$$1 \le r, y, g \le 1\,000$$$, $$$1 \le n \le 10^{9}$$$) — количество секунд, которое на светофоре горит красный, желтый и зеленый свет, соответственно, а также количество секунд, по истечении которого нужно определить состояние светофора.
Для каждого набора входных данных выведите в отдельную строку следующую информацию.
Если в момент времени, который настанет ровно через $$$n$$$ секунд, на светофоре не будет изменяться свет, выведите информацию о свете, который горит на светофоре в этот момент времени: «red» для красного света, «yellow» для желтого света, «green» для зеленого света. Название света выводите без кавычек.
Если в момент времени, который настанет ровно через $$$n$$$ секунд, на светофоре будет меняться свет, то выведите сначала свет, который горел непосредственно до этого момента времени, а затем через пробел выведите информацию о свете, который будет гореть непосредственно после этого момента времени. Если горел красный свет, а будет гореть желтый свет, выведите «red yellow» (без кавычек). Если горел желтый свет, а будет гореть зеленый свет, выведите «yellow green» (без кавычек). Если горел зеленый свет, а будет гореть желтый свет, выведите «green yellow» (без кавычек). Если горел желтый свет, а будет гореть красный свет, выведите «yellow red» (без кавычек).
73 4 2 143 4 2 43 4 2 82 5 1 22 5 1 202 5 1 82 5 1 26
redyellowgreenred yellowyellow greengreen yellowyellow red
Монокарп играет в новую компьютерную игру. В игре у Монокарпа есть прямоугольное поле размера $$$n \times m$$$ (то есть прямоугольное поле состоит из $$$n$$$ строк и $$$m$$$ столбцов).
Известно, что $$$k$$$ клеток поля заняты камнями, остальные клетки поля свободны.
Монокарп хочет разместить на игровом поле постройку, которая представляет собой квадрат $$$2 \times 2$$$. Для того чтобы разместить эту постройку, нужно выбрать четыре свободные клетки на поле, которые формируют квадрат $$$2 \times 2$$$.
Перед вами стоит задача определить количество способов разместить в свободных клетках поля ровно одну постройку размером $$$2 \times 2$$$.
В первой строке следуют три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$2 \le n, m \le 1\,000\,000\,000$$$, $$$1 \le k \le min(200\,000, n \cdot m)$$$) — количество строк и столбцов в поле Монокарпа, а также количество занятых камнями клеток поля.
В $$$i$$$-й из следующих $$$k$$$ строк следуют два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i \le n$$$, $$$1 \le y_i \le m$$$) — координаты $$$i$$$-й занятой клетки. Гарантируется, что среди $$$k$$$ занятых камнями клеток нет одинаковых.
Выведите количество способов разместить ровно одну постройку размером $$$2 \times 2$$$ в свободных клетках на игровом поле.
Обратите внимание, что ответ в этой задаче может не поместиться в стандартный $$$32$$$-битный тип данных. Необходимо использовать $$$64$$$-битный тип данных (long long в C++, int64 в Паскале, long в Java).
3 3 21 33 3
2
3 5 32 42 22 3
0
6 7 42 43 55 13 2
17
1000000000 1000000000 2100 100101 101
999999997999999994
В первом примере можно разместить постройку двумя способами: в клетках $$$[(1, 1), (1, 2), (2, 1), (2, 2)]$$$ или в клетках $$$[(2, 1), (2, 2), (3, 1), (3, 2)]$$$.
Во втором примере невозможно разместить постройку, так как на поле нет ни одного квадрата $$$2 \times 2$$$, состоящего из свободных клеток.
Дано поле $$$n \times m$$$, каждая клетка которого заблокирована или свободна.
Монокарп ставит робота в некоторую свободную клетку поля, а затем запускает его по некоторому циклическому маршруту. За один ход робот может переместиться в свободную клетку, соседнюю по стороне или по углу с текущей. Маршрут должен удовлетворять следующим условиям:
- маршрут должен начинаться и заканчиваться в одной и той же клетке;
- маршрут должен заходить в каждую клетку не более одного раза (считаем, что в начале маршрута робот не заходит в стартовую клетку, а уже там находится);
- робот изменяет направление движения ровно три раза.
Например, робот может начать в некоторой клетке, пойти два раза направо, два раза вниз-влево и два раза наверх. Так как маршрут циклический, робот меняет направление трижды: направо $$$\rightarrow$$$ вниз-влево $$$\rightarrow$$$ наверх $$$\rightarrow$$$ направо.
Два маршрута считаются различными, если:
- либо робот посещает в одном маршруте клетку, которую не посещает в другом;
- либо клетки в маршруте расположены в разном порядке.
Обратите внимание, что маршрут циклический, поэтому два маршрута, отличающиеся только стартовой клеткой, на самом деле не считаются различными.
Сколько различных маршрутов для робота может выбрать Монокарп?
В первой строке записаны два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n, m \le 3 \cdot 10^5$$$; $$$nm \le 3 \cdot 10^5$$$) — размеры поля.
Затем следуют $$$n$$$ строк по $$$m$$$ символов — описание поля. Каждый символ — это либо 'x', обозначающий заблокированную клетку, либо '.', обозначающий свободную клетку.
Выведите одно целое число — количество различных маршрутов робота, которые может выбрать Монокарп.
3 3.x.x.x...
6
4 3x.x..x...x..
32
4 5....................
236
Монокарп хочет нарисовать треугольник с положительной площадью, причем длины всех сторон должны быть целыми числами.
Монокарп знает, что длина первой стороны треугольника будет равна $$$a$$$, а длина второй стороны треугольника будет равна $$$b$$$.
Монокарпу стало интересно, какой может быть минимально возможная и максимально возможная длина третьей стороны треугольника, если эта длина должна быть целым числом, а нарисованный треугольник должен иметь положительную площадь.
В первой строке следует целое число $$$a$$$ ($$$1 \le a \le 1\,000\,000$$$) — длина первой стороны треугольника.
Во второй строке следует целое число $$$b$$$ ($$$1 \le b \le 1\,000\,000$$$) — длина второй стороны треугольника.
Выведите два целых числа — минимально возможную и максимально возможную длину третьей стороны треугольника, если эта длина должна быть целым числом, а нарисованный треугольник должен иметь положительную площадь.
510
6 14
99
1 17
10000001
1000000 1000000
В первом примере длины двух сторон треугольника равны $$$5$$$ и $$$10$$$. Поэтому минимально возможная длина третьей стороны треугольника равна $$$6$$$, а максимально возможная длина третьей стороны треугольника равна $$$14$$$.