Codeforces Round 923 (Div. 3) |
---|
Закончено |
Вам даны два целых числа $$$n$$$ и $$$k$$$ ($$$k \le n$$$), причём число $$$k$$$ — чётное.
Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[0,1,2]$$$ тоже не перестановка ($$$n=3$$$, но в массиве не встречается $$$3$$$).
Ваша задача построить $$$k$$$-ровную перестановку длины $$$n$$$.
Перестановка называется $$$k$$$-ровной, если среди всех сумм непрерывных отрезков длины $$$k$$$ (которых, очевидно, ровно $$$n - k + 1$$$), любые две суммы отличаются не более чем на $$$1$$$.
Более формально, чтобы определить, является ли перестановка $$$p$$$ $$$k$$$-ровной, сначала построим массив $$$s$$$ длины $$$n - k + 1$$$, где $$$s_i=\sum_{j=i}^{i+k-1} p_j$$$, то есть $$$i$$$-й элемент равен сумме $$$p_i, p_{i+1}, \dots, p_{i+k-1}$$$.
Перестановка называется $$$k$$$-ровной, если $$$\max(s) - \min(s) \le 1$$$.
Найдите любую $$$k$$$-ровную перестановку длины $$$n$$$.
Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов.
Первая и единственная строка каждого набора содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le k \le n \le 2 \cdot 10^5$$$, $$$k$$$ — чётное число), где $$$n$$$ — длина искомой перестановки.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите любую $$$k$$$-ровную перестановку длины $$$n$$$.
Гарантируется, что такая перестановка всегда существует при данных ограничениях.
52 23 210 413 47 4
2 1 1 3 2 1 8 4 10 2 7 5 9 3 6 4 10 1 13 5 9 2 12 6 8 3 11 7 1 6 3 7 2 5 4
Во втором наборе входных данных примера:
Название |
---|