codeforces-scrape

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

1927E.md (2078B)


      1 Source: https://codeforces.com/problemset/problem/1927/E
      2 
      3 E. Klever Permutation
      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 You are given two integers $n$ and $k$ ($k \le n$), where $k$ is even.
     22 
     23 A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in any order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation (as $2$ appears twice in the array) and $[0,1,2]$ is also not a permutation (as $n=3$, but $3$ is not present in the array).
     24 
     25 Your task is to construct a $k$-level permutation of length $n$.
     26 
     27 A permutation is called $k$-level if, among all the sums of continuous segments of length $k$ (of which there are exactly $n - k + 1$), any two sums differ by no more than $1$.
     28 
     29 More formally, to determine if the permutation $p$ is $k$-level, first construct an array $s$ of length $n - k + 1$, where $s_i=\sum_{j=i}^{i+k-1} p_j$, i.e., the $i$-th element is equal to the sum of $p_i, p_{i+1}, \dots, p_{i+k-1}$.
     30 
     31 A permutation is called $k$-level if $\max(s) - \min(s) \le 1$.
     32 
     33 Find any $k$-level permutation of length $n$.
     34 
     35 Input
     36 
     37 The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. This is followed by the description of the test cases.
     38 
     39 The first and only line of each test case contains two integers $n$ and $k$ ($2 \le k \le n \le 2 \cdot 10^5$, $k$ is even), where $n$ is the length of the desired permutation.
     40 
     41 It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$.
     42 
     43 Output
     44 
     45 For each test case, output any $k$-level permutation of length $n$.
     46 
     47 It is guaranteed that such a permutation always exists given the constraints.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 5
     55 
     56 2 2
     57 
     58 3 2
     59 
     60 10 4
     61 
     62 13 4
     63 
     64 7 4
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 2 1
     71 1 3 2
     72 1 8 4 10 2 7 5 9 3 6
     73 4 10 1 13 5 9 2 12 6 8 3 11 7
     74 1 6 3 7 2 5 4
     75 ```
     76 
     77 Note
     78 
     79 In the second test case of the example:
     80 
     81 * $p_1 + p_2 = 3 + 1 = 4$;
     82 * $p_2 + p_3 = 1 + 2 = 3$.
     83 
     84 The maximum among the sums is $4$, and the minimum is $3$.