Codeforces Round 852 (Div. 2) |
---|
Закончено |
Недавно Феде на день рождения подарили массив $$$a$$$ из $$$n$$$ целых чисел, записаных по кругу, в котором для каждой пары соседних элементов ($$$a_1$$$ и $$$a_2$$$, $$$a_2$$$ и $$$a_3$$$, $$$\ldots$$$, $$$a_{n - 1}$$$ и $$$a_n$$$, $$$a_n$$$ и $$$a_1$$$) модуль их разности равен $$$1$$$.
Назовём локальным максимумом элемент, который больше обоих соседних элементов. Также назовём локальным минимумом элемент, который меньше обоих соседних элементов. Обратите внимание, что элементы $$$a_1$$$ и $$$a_n$$$ являются соседними.
К сожалению, Федя потерял массив, но он запомнил в нём сумму локальных максимумов $$$x$$$ и сумму локальных минимумов $$$y$$$.
По заданным $$$x$$$ и $$$y$$$ помогите Феде найти любой подходящий массив минимальной длины.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Каждая строка каждого набора входных данных содержит два целых числа $$$x$$$ и $$$y$$$ ($$$-10^{9} \le y < x \le 10^{9}$$$) — сумму локальных максимумов и сумму локальных минимумов, соотвественно.
Для каждого набора входных данных в первой строке выведите одно число $$$n$$$ — минимальную длину подходящего массива.
Во второй строке выведите $$$n$$$ чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^{9} \leqslant a_i \leqslant 10^{9}$$$) — элементы массива, такие что модуль разности каждой пары соседних равен $$$1$$$.
Если существуют несколько решений, выведите любое из них.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^{5}$$$.
43 -24 -42 -15 -3
10 0 1 2 1 0 -1 0 -1 0 1 16 -2 -1 -2 -1 0 1 2 3 4 5 4 3 2 1 0 -1 6 1 0 -1 0 1 0 16 2 3 2 1 0 -1 0 -1 0 -1 0 1 2 1 0 1
В первом наборе входных данных локальными максимумами являются числа на позициях $$$3, 7$$$ и $$$10$$$, а локальными минимумами числа на позициях $$$1, 6$$$ и $$$8$$$. $$$x = a_3 + a_7 + a_{10} = 2 + 0 + 1 = 3$$$, $$$y = a_1 + a_6 + a_8 = 0 + (-1) + (-1) = -2$$$.
Во втором наборе входных данных локальными максимумами являются числа на позициях $$$2$$$ и $$$10$$$, а локальными минимумами числа на позициях $$$1$$$ и $$$3$$$. $$$x = a_2 + a_{10} = -1 + 5 = 4$$$, $$$y = a_1 + a_3 = -2 + (-2) = -4$$$.
В третьем наборе входных данных локальными максимумами являются числа на позициях $$$1$$$ и $$$5$$$, а локальными минимумами числа на позициях $$$3$$$ и $$$6$$$.
Название |
---|