1793B.md (2531B)
1 Source: https://codeforces.com/problemset/problem/1793/B 2 3 B. Fedya and Array 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 For his birthday recently Fedya was given an array $a$ of $n$ integers arranged in a circle, For each pair of neighboring numbers ($a_1$ and $a_2$, $a_2$ and $a_3$, $\ldots$, $a_{n - 1}$ and $a_n$, $a_n$ and $a_1$) the absolute difference between them is equal to $1$. 22 23 Let's call a local maximum an element, which is greater than both of its neighboring elements. Also call a local minimum an element, which is less than both of its neighboring elements. Note, that elements $a_1$ and $a_n$ are neighboring elements. 24 25 Unfortunately, Fedya lost an array, but he remembered in it the sum of local maximums $x$ and the sum of local minimums $y$. 26 27 Given $x$ and $y$, help Fedya find any matching array of minimum length. 28 29 Input 30 31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). Description of the test cases follows. 32 33 Each line of each test case contain two integers $x$ and $y$ ($-10^{9} \le y \lt x \le 10^{9}$) — the sum of local maximums and the sum of local minimums, respectively. 34 35 Output 36 37 For each test case, in the first line print one integer $n$ — the minimum length of matching arrays. 38 39 In the second line print $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^{9} \leqslant a_i \leqslant 10^{9}$) — the array elements such that the the absolute difference between each pair of neighboring is equal to $1$. 40 41 If there are multiple solutions, print any of them. 42 43 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^{5}$. 44 45 Example 46 47 Input 48 49 ``` 50 4 51 52 3 -2 53 54 4 -4 55 56 2 -1 57 58 5 -3 59 ``` 60 61 Output 62 63 ``` 64 10 65 0 1 2 1 0 -1 0 -1 0 1 66 16 67 -2 -1 -2 -1 0 1 2 3 4 5 4 3 2 1 0 -1 68 6 69 1 0 -1 0 1 0 70 16 71 2 3 2 1 0 -1 0 -1 0 -1 0 1 2 1 0 1 72 ``` 73 74 Note 75 76 In the first test case, the local maximums are the numbers at $3, 7$ and $10$ positions, and the local minimums are the numbers at $1, 6$ and $8$ positions. $x = a_3 + a_7 + a_{10} = 2 + 0 + 1 = 3$, $y = a_1 + a_6 + a_8 = 0 + (-1) + (-1) = -2$. 77 78 In the second test case, the local maximums are the numbers at $2$ and $10$ positions, and the local minimums are the numbers at $1$ and $3$ positions. $x = a_2 + a_{10} = -1 + 5 = 4$, $y = a_1 + a_3 = -2 + (-2) = -4$. 79 80 In the third test case, the local maximums are the numbers at $1$ and $5$ positions, and the local minimums are the numbers at $3$ and $6$ positions.