codeforces-scrape

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

1857C.md (1950B)


      1 Source: https://codeforces.com/problemset/problem/1857/C
      2 
      3 C. Assembly via Minimums
      4 
      5 time limit per test
      6 
      7 2 seconds
      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 Sasha has an array $a$ of $n$ integers. He got bored and for all $i$, $j$ ($i \lt j$), he wrote down the minimum value of $a_i$ and $a_j$. He obtained a new array $b$ of size $\frac{n\cdot (n-1)}{2}$.
     22 
     23 For example, if $a=$ [$2,3,5,1$], he would write [$\min(2, 3), \min(2, 5), \min(2, 1), \min(3, 5), \min(3, 1), min(5, 1)$] $=$ [$2, 2, 1, 3, 1, 1$].
     24 
     25 Then, he randomly shuffled all the elements of the array $b$.
     26 
     27 Unfortunately, he forgot the array $a$, and your task is to restore any possible array $a$ from which the array $b$ could have been obtained.
     28 
     29 The elements of array $a$ should be in the range $[-10^9,10^9]$.
     30 
     31 Input
     32 
     33 The first line contains a single integer $t$ ($1\le t\le 200$) — the number of test cases.
     34 
     35 The first line of each test case contains a single integer $n$ ($2\le n\le 10^3$) — the length of array $a$.
     36 
     37 The second line of each test case contains $\frac{n\cdot (n-1)}{2}$ integers $b_1,b_2,\dots,b_{\frac{n\cdot (n-1)}{2}}$ ($−10^9\le b_i\le 10^9$) — the elements of array $b$.
     38 
     39 It is guaranteed that the sum of $n$ over all tests does not exceed $10^3$ and for each array $b$ in the test, there exists an original array.
     40 
     41 Output
     42 
     43 For each test case, output any possible array $a$ of length $n$.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 5
     51 
     52 3
     53 
     54 1 3 1
     55 
     56 2
     57 
     58 10
     59 
     60 4
     61 
     62 7 5 3 5 3 3
     63 
     64 5
     65 
     66 2 2 2 2 2 2 2 2 2 2
     67 
     68 5
     69 
     70 3 0 0 -2 0 -2 0 0 -2 -2
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 1 3 3
     77 10 10
     78 7 5 3 12
     79 2 2 2 2 2
     80 0 -2 0 3 5
     81 ```
     82 
     83 Note
     84 
     85 In the first sample, Sasha chose the array $[1,3,3]$, then the array $b$ will look like $[\min(a_1,a_2)=1, \min(a_1,a_3)=1, \min(a_2,a_3)=3]$, after shuffling its elements, the array can look like $[1,3,1]$.
     86 
     87 In the second sample, there is only one pair, so the array $[10,10]$ is suitable. Another suitable array could be $[15,10]$.