codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.