1809C.md (1322B)
1 Source: https://codeforces.com/problemset/problem/1809/C 2 3 C. Sum on Subarrays 4 5 time limit per test 6 7 2 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 For an array $a = [a_1, a_2, \dots, a_n]$, let's denote its subarray $a[l, r]$ as the array $[a_l, a_{l+1}, \dots, a_r]$. 22 23 For example, the array $a = [1, -3, 1]$ has $6$ non-empty subarrays: 24 25 * $a[1,1] = [1]$; 26 * $a[1,2] = [1,-3]$; 27 * $a[1,3] = [1,-3,1]$; 28 * $a[2,2] = [-3]$; 29 * $a[2,3] = [-3,1]$; 30 * $a[3,3] = [1]$. 31 32 You are given two integers $n$ and $k$. Construct an array $a$ consisting of $n$ integers such that: 33 34 * all elements of $a$ are from $-1000$ to $1000$; 35 * $a$ has exactly $k$ subarrays with positive sums; 36 * the rest $\dfrac{(n+1) \cdot n}{2}-k$ subarrays of $a$ have negative sums. 37 38 Input 39 40 The first line contains one integer $t$ ($1 \le t \le 5000$) — the number of test cases. 41 42 Each test case consists of one line containing two integers $n$ and $k$ ($2 \le n \le 30$; $0 \le k \le \dfrac{(n+1) \cdot n}{2}$). 43 44 Output 45 46 For each test case, print $n$ integers — the elements of the array meeting the constraints. It can be shown that the answer always exists. If there are multiple answers, print any of them. 47 48 Example 49 50 Input 51 52 ``` 53 4 54 55 3 2 56 57 2 0 58 59 2 2 60 61 4 6 62 ``` 63 64 Output 65 66 ``` 67 1 -3 1 68 -13 -42 69 -13 42 70 -3 -4 10 -2 71 ```