codeforces-scrape

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

1991C.md (2783B)


      1 Source: https://codeforces.com/problemset/problem/1991/C
      2 
      3 C. Absolute Zero
      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 You are given an array $a$ of $n$ integers.
     22 
     23 In one operation, you will perform the following two-step move:
     24 
     25 1. Choose an integer $x$ ($0 \le x \le 10^{9}$).
     26 2. Replace each $a_i$ with $|a_i - x|$, where $|v|$ denotes the [absolute value](https://en.wikipedia.org/wiki/Absolute_value) of $v$.
     27 
     28 For example, by choosing $x = 8$, the array $[5, 7, 10]$ will be changed into $[|5-8|, |7-8|, |10-8|] = [3,1,2]$.
     29 
     30 Construct a sequence of operations to make all elements of $a$ equal to $0$ in at most $40$ operations or determine that it is impossible. You do not need to minimize the number of operations.
     31 
     32 Input
     33 
     34 Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of test cases follows.
     35 
     36 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the array $a$.
     37 
     38 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — the elements of the array $a$.
     39 
     40 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     41 
     42 Output
     43 
     44 For each test case, output a single integer $-1$ if it is impossible to make all array elements equal to $0$ in at most $40$ operations.
     45 
     46 Otherwise, output two lines. The first line of output should contain a single integer $k$ ($0 \le k \le 40$) — the number of operations. The second line of output should contain $k$ integers $x_1, x_2, \ldots, x_k$ ($0 \le x_i \le 10^{9}$) — the sequence of operations, denoting that on the $i$-th operation, you chose $x=x_i$.
     47 
     48 If there are multiple solutions, output any of them.
     49 
     50 You do not need to minimize the number of operations.
     51 
     52 Example
     53 
     54 Input
     55 
     56 ```
     57 5
     58 
     59 1
     60 
     61 5
     62 
     63 2
     64 
     65 0 0
     66 
     67 3
     68 
     69 4 6 8
     70 
     71 4
     72 
     73 80 40 20 10
     74 
     75 5
     76 
     77 1 2 3 4 5
     78 ```
     79 
     80 Output
     81 
     82 ```
     83 1
     84 5
     85 0
     86 
     87 3
     88 6 1 1
     89 7
     90 60 40 20 10 30 25 5
     91 -1
     92 ```
     93 
     94 Note
     95 
     96 In the first test case, we can perform only one operation by choosing $x = 5$, changing the array from $[5]$ to $[0]$.
     97 
     98 In the second test case, no operations are needed because all elements of the array are already $0$.
     99 
    100 In the third test case, we can choose $x = 6$ to change the array from $[4, 6, 8]$ to $[2, 0, 2]$, then choose $x = 1$ to change it to $[1, 1, 1]$, and finally choose $x = 1$ again to change the array into $[0, 0, 0]$.
    101 
    102 In the fourth test case, we can make all elements $0$ by following the operation sequence $(60, 40, 20, 10, 30, 25, 5)$.
    103 
    104 In the fifth test case, it can be shown that it is impossible to make all elements $0$ in at most $40$ operations. Therefore, the output is $-1$.