codeforces-scrape

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

1512E.md (1888B)


      1 Source: https://codeforces.com/problemset/problem/1512/E
      2 
      3 E. Permutation by Sum
      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 A permutation is a sequence of $n$ integers from $1$ to $n$, in which all the numbers occur exactly once. For example, $[1]$, $[3, 5, 2, 1, 4]$, $[1, 3, 2]$ are permutations, and $[2, 3, 2]$, $[4, 3, 1]$, $[0]$ are not.
     22 
     23 Polycarp was given four integers $n$, $l$, $r$ ($1 \le l \le r \le n)$ and $s$ ($1 \le s \le \frac{n (n+1)}{2}$) and asked to find a permutation $p$ of numbers from $1$ to $n$ that satisfies the following condition:
     24 
     25 * $s = p_l + p_{l+1} + \ldots + p_r$.
     26 
     27 For example, for $n=5$, $l=3$, $r=5$, and $s=8$, the following permutations are suitable (not all options are listed):
     28 
     29 * $p = [3, 4, 5, 2, 1]$;
     30 * $p = [5, 2, 4, 3, 1]$;
     31 * $p = [5, 2, 1, 3, 4]$.
     32 
     33 But, for example, there is no permutation suitable for the condition above for $n=4$, $l=1$, $r=1$, and $s=5$.
     34 
     35 Help Polycarp, for the given $n$, $l$, $r$, and $s$, find a permutation of numbers from $1$ to $n$ that fits the condition above. If there are several suitable permutations, print any of them.
     36 
     37 Input
     38 
     39 The first line contains a single integer $t$ ($1 \le t \le 500$). Then $t$ test cases follow.
     40 
     41 Each test case consist of one line with four integers $n$ ($1 \le n \le 500$), $l$ ($1 \le l \le n$), $r$ ($l \le r \le n$), $s$ ($1 \le s \le \frac{n (n+1)}{2}$).
     42 
     43 It is guaranteed that the sum of $n$ for all input data sets does not exceed $500$.
     44 
     45 Output
     46 
     47 For each test case, output on a separate line:
     48 
     49 * $n$ integers — a permutation of length $n$ that fits the condition above if such a permutation exists;
     50 * -1, otherwise.
     51 
     52 If there are several suitable permutations, print any of them.
     53 
     54 Example
     55 
     56 Input
     57 
     58 ```
     59 5
     60 5 2 3 5
     61 5 3 4 1
     62 3 1 2 4
     63 2 2 2 2
     64 2 1 1 3
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 1 2 3 4 5 
     71 -1
     72 1 3 2 
     73 1 2 
     74 -1
     75 ```