codeforces-scrape

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

1772C.md (1486B)


      1 Source: https://codeforces.com/problemset/problem/1772/C
      2 
      3 C. Different Differences
      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 An array $a$ consisting of $k$ integers is strictly increasing if $a_1 \lt a_2 \lt \dots \lt a_k$. For example, the arrays $[1, 3, 5]$, $[1, 2, 3, 4]$, $[3, 5, 6]$ are strictly increasing; the arrays $[2, 2]$, $[3, 7, 5]$, $[7, 4, 3]$, $[1, 2, 2, 3]$ are not.
     22 
     23 For a strictly increasing array $a$ of $k$ elements, let's denote the characteristic as the number of different elements in the array $[a_2 - a_1, a_3 - a_2, \dots, a_k - a_{k-1}]$. For example, the characteristic of the array $[1, 3, 4, 7, 8]$ is $3$ since the array $[2, 1, 3, 1]$ contains $3$ different elements: $2$, $1$ and $3$.
     24 
     25 You are given two integers $k$ and $n$ ($k \le n$). Construct an increasing array of $k$ integers from $1$ to $n$ with maximum possible characteristic.
     26 
     27 Input
     28 
     29 The first line contains one integer $t$ ($1 \le t \le 819$) — the number of test cases.
     30 
     31 Each test case consists of one line containing two integers $k$ and $n$ ($2 \le k \le n \le 40$).
     32 
     33 Output
     34 
     35 For each test case, print $k$ integers — the elements of the strictly increasing array $a$ with the maximum possible characteristic. If there are multiple answers, print any of them.
     36 
     37 Example
     38 
     39 Input
     40 
     41 ```
     42 7
     43 
     44 5 9
     45 
     46 4 12
     47 
     48 3 3
     49 
     50 3 4
     51 
     52 4 4
     53 
     54 4 6
     55 
     56 8 11
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 1 3 4 7 8
     63 2 4 7 12
     64 1 2 3
     65 1 3 4
     66 1 2 3 4
     67 2 4 5 6
     68 1 2 3 5 6 7 8 11
     69 ```