codeforces-scrape

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

2130B.md (2459B)


      1 Source: https://codeforces.com/problemset/problem/2130/B
      2 
      3 B. Pathless
      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 There is an array $a_1, a_2, \ldots, a_n$ consisting of values $0$, $1$, and $2$, and an integer $s$. It is guaranteed that $a_1, a_2, \ldots, a_n$ contains at least one $0$, one $1$, and one $2$.
     22 
     23 Alice wants to start from index $1$ and perform steps of length $1$ to the right or to the left, and reach index $n$ at the end. While Alice moves, she calculates the sum of the values she is visiting, and she wants the sum to be exactly $s$.
     24 
     25 Formally, Alice wants to find a sequence $[i_1, i_2, \ldots, i_m]$ of indices, such that:
     26 
     27 * $i_1 = 1$, $i_m = n$.
     28 * $1 \leq i_j \leq n$ for all $1 \le j \le m$.
     29 * $|i_{j} - i_{j+1}| = 1$ for all $1 \leq j \lt m$.
     30 * $a_{i_1} + a_{i_2} + \ldots + a_{i_m} = s$.
     31 
     32 However, Bob wants to rearrange $a_1, a_2, \ldots, a_n$ to prevent Alice from achieving her target. Determine whether it is possible to rearrange $a_1, a_2, \ldots, a_n$ such that Alice cannot find her target sequence (even if Alice is smart enough). If it is possible, you also need to output the rearranged array $a_1, a_2, \ldots, a_n$.
     33 
     34 Input
     35 
     36 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.
     37 
     38 The first line of each test case contains two integers $n$ and $s$ ($3 \le n \le 50$, $0 \le s \le 1000$).
     39 
     40 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 2$).
     41 
     42 It is guaranteed that $a$ contains at least one $0$, one $1$, and one $2$.
     43 
     44 Output
     45 
     46 For each test case, if it is possible to rearrange $a$ such that Alice cannot find her target sequence, output $n$ integers — such rearrangement of $a$. Otherwise, output $-1$ instead.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 6
     54 
     55 3 2
     56 
     57 0 1 2
     58 
     59 3 3
     60 
     61 0 1 2
     62 
     63 3 6
     64 
     65 0 1 2
     66 
     67 3 4
     68 
     69 0 1 2
     70 
     71 3 10
     72 
     73 0 1 2
     74 
     75 5 1000
     76 
     77 2 0 1 1 2
     78 ```
     79 
     80 Output
     81 
     82 ```
     83 0 1 2
     84 -1
     85 -1
     86 0 2 1 
     87 -1
     88 -1
     89 ```
     90 
     91 Note
     92 
     93 In the first test case, any rearrangement of $a$ can prevent Alice from achieving her target.
     94 
     95 In the second test case, regardless of rearranging $a$, Alice can always find the sequence $[1,2,3]$ as her target sequence.
     96 
     97 In the third test case,there is no rearrangement of $a$ that can prevent Alice from achieving her target. For example, for $a=[0,2,1]$, Alice can find the sequence $[1,2,3,2,3]$ as her target sequence.