codeforces-scrape

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

1455D.md (1909B)


      1 Source: https://codeforces.com/problemset/problem/1455/D
      2 
      3 D. Sequence and Swaps
      4 
      5 time limit per test
      6 
      7 1.5 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given a sequence $a$ consisting of $n$ integers $a_1, a_2, \dots, a_n$, and an integer $x$. Your task is to make the sequence $a$ sorted (it is considered sorted if the condition $a_1 \le a_2 \le a_3 \le \dots \le a_n$ holds).
     22 
     23 To make the sequence sorted, you may perform the following operation any number of times you want (possibly zero): choose an integer $i$ such that $1 \le i \le n$ and $a_i \gt x$, and swap the values of $a_i$ and $x$.
     24 
     25 For example, if $a = [0, 2, 3, 5, 4]$, $x = 1$, the following sequence of operations is possible:
     26 
     27 1. choose $i = 2$ (it is possible since $a_2 \gt x$), then $a = [0, 1, 3, 5, 4]$, $x = 2$;
     28 2. choose $i = 3$ (it is possible since $a_3 \gt x$), then $a = [0, 1, 2, 5, 4]$, $x = 3$;
     29 3. choose $i = 4$ (it is possible since $a_4 \gt x$), then $a = [0, 1, 2, 3, 4]$, $x = 5$.
     30 
     31 Calculate the minimum number of operations you have to perform so that $a$ becomes sorted, or report that it is impossible.
     32 
     33 Input
     34 
     35 The first line contains one integer $t$ ($1 \le t \le 500$) — the number of test cases.
     36 
     37 Each test case consists of two lines. The first line contains two integers $n$ and $x$ ($1 \le n \le 500$, $0 \le x \le 500$) — the number of elements in the sequence and the initial value of $x$.
     38 
     39 The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($0 \le a_i \le 500$).
     40 
     41 The sum of values of $n$ over all test cases in the input does not exceed $500$.
     42 
     43 Output
     44 
     45 For each test case, print one integer — the minimum number of operations you have to perform to make $a$ sorted, or $-1$, if it is impossible.
     46 
     47 Example
     48 
     49 Input
     50 
     51 ```
     52 6
     53 4 1
     54 2 3 5 4
     55 5 6
     56 1 1 3 4 4
     57 1 10
     58 2
     59 2 10
     60 11 9
     61 2 10
     62 12 11
     63 5 18
     64 81 324 218 413 324
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 3
     71 0
     72 0
     73 -1
     74 1
     75 3
     76 ```