Codeforces Round 580 (Div. 1) |
---|
Закончено |
Назовем красотой перестановки чисел от $$$1$$$ до $$$n$$$ $$$(p_1, p_2, \dots, p_n)$$$ количество пар $$$(L, R)$$$ таких, что $$$1 \le L \le R \le n$$$ и числа $$$p_L, p_{L+1}, \dots, p_R$$$ являются последовательными $$$R-L+1$$$ числами в каком-то порядке. К примеру, красота перестановки $$$(1, 2, 5, 3, 4)$$$ равна $$$9$$$, а отрезки, соответствующие парам индексов — это $$$[1]$$$, $$$[2]$$$, $$$[5]$$$, $$$[4]$$$, $$$[3]$$$, $$$[1, 2]$$$, $$$[3, 4]$$$, $$$[5, 3, 4]$$$, $$$[1, 2, 5, 3, 4]$$$.
Вам нужно ответить на $$$q$$$ независимых запросов. В каждом запросе вам будут даны целые положительные числа $$$n$$$, $$$k$$$. Определите, существует ли перестановка чисел от $$$1$$$ до $$$n$$$ с красотой, равной $$$k$$$, а если существует, то выведите одну из таких.
Первая строка содержит целое число $$$q$$$ ($$$1\le q \le 10\,000$$$) — число запросов.
Далее следует $$$q$$$ строк. Каждая строка содержит два целых числа $$$n$$$, $$$k$$$ ($$$1 \le n \le 100$$$, $$$1 \le k \le \frac{n(n+1)}{2}$$$) — длину перестановки и необходимую красоту соответственно.
Для запроса выведите «NO», если не существует нужной перестановки. Иначе выведите «YES», а в следующей строке выведите $$$n$$$ чисел — элементы перестановки в нужном порядке.
4 1 1 5 6 5 8 5 10
YES 1 YES 2 4 1 5 3 NO YES 2 3 1 4 5
2 4 10 100 1
YES 1 2 3 4 NO
Посмотрим на первый пример.
Первый запрос: в $$$(1)$$$ есть только один отрезок, состоящий из последовательных чисел — вся перестановка.
Второй запрос: в $$$(2, 4, 1, 5, 3)$$$ есть $$$6$$$ таких отрезков: $$$[2]$$$, $$$[4]$$$, $$$[1]$$$, $$$[5]$$$, $$$[3]$$$, $$$[2, 4, 1, 5, 3]$$$.
Для третьего запроса таких перестановок не существует.
Четвертый запрос: в $$$(2, 3, 1, 4, 5)$$$ есть $$$10$$$ таких отрезков: $$$[2]$$$, $$$[3]$$$, $$$[1]$$$, $$$[4]$$$, $$$[5]$$$, $$$[2, 3]$$$, $$$[2, 3, 1]$$$, $$$[2, 3, 1, 4]$$$, $$$[4, 5]$$$, $$$[2, 3, 1, 4, 5]$$$.
Название |
---|