codeforces-scrape

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

2112B.md (2079B)


      1 Source: https://codeforces.com/problemset/problem/2112/B
      2 
      3 B. Shrinking Array
      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 Let's call an array $b$ beautiful if it consists of at least two elements and there exists a position $i$ such that $|b_i - b_{i + 1}| \le 1$ (where $|x|$ is the absolute value of $x$).
     22 
     23 You are given an array $a$, and as long as it consists of at least two elements, you can perform the following operation:
     24 
     25 1. Choose two adjacent positions $i$ and $i + 1$ in the array $a$.
     26 2. Choose an integer $x$ such that $\min(a_i, a_{i + 1}) \le x \le \max(a_i, a_{i + 1})$.
     27 3. Remove the numbers $a_i$ and $a_{i + 1}$ from the array, and insert the number $x$ in their place. Obviously, the size of the array will decrease by $1$.
     28 
     29 Calculate the minimum number of operations required to make the array beautiful, or report that it is impossible.
     30 
     31 Input
     32 
     33 The first line contains one integer $t$ ($1 \le t \le 200$) — the number of test cases.
     34 
     35 The first line of each test case contains one integer $n$ ($2 \le n \le 1000$) — the size of the array $a$.
     36 
     37 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — the array $a$ itself.
     38 
     39 Output
     40 
     41 For each test case, output one integer — the minimum number of operations needed to make the array $a$ beautiful, or $-1$ if it is impossible to make it beautiful.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 4
     49 
     50 4
     51 
     52 1 3 3 7
     53 
     54 2
     55 
     56 6 9
     57 
     58 4
     59 
     60 3 1 3 7
     61 
     62 4
     63 
     64 1 3 5 2
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 0
     71 -1
     72 1
     73 1
     74 ```
     75 
     76 Note
     77 
     78 In the first test case, the given array is already beautiful, as $|a_2 - a_3| = |3 - 3| = 0$.
     79 
     80 In the second test case, it is impossible to make the array beautiful, as applying the operation would reduce its size to less than two.
     81 
     82 In the third test case, you can, for example, choose $a_1$ and $a_2$ and replace them with the number $2$. The resulting array $[2, 3, 7]$ is beautiful.
     83 
     84 In the fourth test case, you can, for example, choose $a_2$ and $a_3$ and replace them with the number $3$. The resulting array $[1, 3, 2]$ is beautiful.