codeforces-scrape

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

1339B.md (1737B)


      1 Source: https://codeforces.com/problemset/problem/1339/B
      2 
      3 B. Sorted Adjacent Differences
      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 You have array of $n$ numbers $a_{1}, a_{2}, \ldots, a_{n}$.
     22 
     23 Rearrange these numbers to satisfy $|a_{1} - a_{2}| \le |a_{2} - a_{3}| \le \ldots \le |a_{n-1} - a_{n}|$, where $|x|$ denotes absolute value of $x$. It's always possible to find such rearrangement.
     24 
     25 Note that all numbers in $a$ are not necessarily different. In other words, some numbers of $a$ may be same.
     26 
     27 You have to answer independent $t$ test cases.
     28 
     29 Input
     30 
     31 The first line contains a single integer $t$ ($1 \le t \le 10^{4}$) — the number of test cases.
     32 
     33 The first line of each test case contains single integer $n$ ($3 \le n \le 10^{5}$) — the length of array $a$. It is guaranteed that the sum of values of $n$ over all test cases in the input does not exceed $10^{5}$.
     34 
     35 The second line of each test case contains $n$ integers $a_{1}, a_{2}, \ldots, a_{n}$ ($-10^{9} \le a_{i} \le 10^{9}$).
     36 
     37 Output
     38 
     39 For each test case, print the rearranged version of array $a$ which satisfies given condition. If there are multiple valid rearrangements, print any of them.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 2
     47 6
     48 5 -2 4 8 6 5
     49 4
     50 8 1 4 2
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 5 5 4 6 8 -2
     57 1 2 4 8
     58 ```
     59 
     60 Note
     61 
     62 In the first test case, after given rearrangement, $|a_{1} - a_{2}| = 0 \le |a_{2} - a_{3}| = 1 \le |a_{3} - a_{4}| = 2 \le |a_{4} - a_{5}| = 2 \le |a_{5} - a_{6}| = 10$. There are other possible answers like "5 4 5 6 -2 8".
     63 
     64 In the second test case, after given rearrangement, $|a_{1} - a_{2}| = 1 \le |a_{2} - a_{3}| = 2 \le |a_{3} - a_{4}| = 4$. There are other possible answers like "2 4 8 1".