310014: CF1772C. Different Differences

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Different Differences

题意翻译

共 $t$ 组询问,定义一个数组的特征数为 **相邻两数差的不同值的个数**。例如数组 $[1,3,4,7,8]$ 的相邻数差为 $[2,1,3,1]$,共有 $3$ 个不同的值,即原数组的特征数为 $3$。构造一个长度为 $k$ 且数组中每个数都不超过 $n$ 的一个 **严格递增数组**,使其的特征数尽可能大。输出这个数组。 $1\le t\le 819,1\le k\le n\le 40$。

题目描述

An array $ a $ consisting of $ k $ integers is strictly increasing if $ a_1 < a_2 < \dots < 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. 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 $ . 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.

输入输出格式

输入格式


The first line contains one integer $ t $ ( $ 1 \le t \le 819 $ ) — the number of test cases. Each test case consists of one line containing two integers $ k $ and $ n $ ( $ 2 \le k \le n \le 40 $ ).

输出格式


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.

输入输出样例

输入样例 #1

7
5 9
4 12
3 3
3 4
4 4
4 6
8 11

输出样例 #1

1 3 4 7 8
2 4 7 12
1 2 3
1 3 4
1 2 3 4
2 4 5 6
1 2 3 5 6 7 8 11

Input

题意翻译

共 $t$ 组询问,定义一个数组的特征数为 **相邻两数差的不同值的个数**。例如数组 $[1,3,4,7,8]$ 的相邻数差为 $[2,1,3,1]$,共有 $3$ 个不同的值,即原数组的特征数为 $3$。构造一个长度为 $k$ 且数组中每个数都不超过 $n$ 的一个 **严格递增数组**,使其的特征数尽可能大。输出这个数组。 $1\le t\le 819,1\le k\le n\le 40$。

Output

**题意翻译**

题目要求构造一个长度为 $ k $ 且数组中每个数都不超过 $ n $ 的一个 **严格递增数组**,使其的特征数尽可能大。特征数定义为 **相邻两数差的不同值的个数**。例如,数组 $[1,3,4,7,8]$ 的相邻数差为 $[2,1,3,1]$,共有 $3$ 个不同的值,即原数组的特征数为 $3$。需要输出这个数组。

输入数据格式:共 $ t $ 组询问,每组询问包含两个整数 $ k $ 和 $ n $。

输出数据格式:对于每组询问,输出一个满足条件的严格递增数组。

$1\le t\le 819,1\le k\le n\le 40$。

**题目描述**

一个由 $ k $ 个整数组成的数组 $ a $ 如果满足 $ a_1 < a_2 < \dots < a_k $,则称为严格递增数组。例如,数组 $[1, 3, 5]$、$[1, 2, 3, 4]$、$[3, 5, 6]$ 都是严格递增的;而数组 $[2, 2]$、$[3, 7, 5]$、$[7, 4, 3]$、$[1, 2, 2, 3]$ 则不是。

对于一个严格递增数组 $ a $,其特征数定义为数组 $[a_2 - a_1, a_3 - a_2, \dots, a_k - a_{k-1}]$ 中不同元素的数量。例如,数组 $[1, 3, 4, 7, 8]$ 的特征数为 $3$,因为数组 $[2, 1, 3, 1]$ 包含 $3$ 个不同的元素:$2$、$1$ 和 $3$。

给定两个整数 $ k $ 和 $ n $($ k \le n $),构造一个从 $1$ 到 $n$ 的 $ k $ 个整数的递增数组,使其特征数尽可能大。

**输入输出格式**

- **输入格式**:第一行包含一个整数 $ t $($ 1 \le t \le 819 $)——测试用例的数量。每个测试用例包含一行,有两个整数 $ k $ 和 $ n $($ 2 \le k \le n \le 40 $)。

- **输出格式**:对于每个测试用例,输出 $ k $ 个整数——严格递增数组 $ a $ 的元素,使其特征数尽可能大。如果有多个答案,输出其中任意一个。

**输入输出样例**

- **输入样例 #1**:
```
7
5 9
4 12
3 3
3 4
4 4
4 6
8 11
```

- **输出样例 #1**:
```
1 3 4 7 8
2 4 7 12
1 2 3
1 3 4
1 2 3 4
2 4 5 6
1 2 3 5 6 7 8 11
```**题意翻译** 题目要求构造一个长度为 $ k $ 且数组中每个数都不超过 $ n $ 的一个 **严格递增数组**,使其的特征数尽可能大。特征数定义为 **相邻两数差的不同值的个数**。例如,数组 $[1,3,4,7,8]$ 的相邻数差为 $[2,1,3,1]$,共有 $3$ 个不同的值,即原数组的特征数为 $3$。需要输出这个数组。 输入数据格式:共 $ t $ 组询问,每组询问包含两个整数 $ k $ 和 $ n $。 输出数据格式:对于每组询问,输出一个满足条件的严格递增数组。 $1\le t\le 819,1\le k\le n\le 40$。 **题目描述** 一个由 $ k $ 个整数组成的数组 $ a $ 如果满足 $ a_1 < a_2 < \dots < a_k $,则称为严格递增数组。例如,数组 $[1, 3, 5]$、$[1, 2, 3, 4]$、$[3, 5, 6]$ 都是严格递增的;而数组 $[2, 2]$、$[3, 7, 5]$、$[7, 4, 3]$、$[1, 2, 2, 3]$ 则不是。 对于一个严格递增数组 $ a $,其特征数定义为数组 $[a_2 - a_1, a_3 - a_2, \dots, a_k - a_{k-1}]$ 中不同元素的数量。例如,数组 $[1, 3, 4, 7, 8]$ 的特征数为 $3$,因为数组 $[2, 1, 3, 1]$ 包含 $3$ 个不同的元素:$2$、$1$ 和 $3$。 给定两个整数 $ k $ 和 $ n $($ k \le n $),构造一个从 $1$ 到 $n$ 的 $ k $ 个整数的递增数组,使其特征数尽可能大。 **输入输出格式** - **输入格式**:第一行包含一个整数 $ t $($ 1 \le t \le 819 $)——测试用例的数量。每个测试用例包含一行,有两个整数 $ k $ 和 $ n $($ 2 \le k \le n \le 40 $)。 - **输出格式**:对于每个测试用例,输出 $ k $ 个整数——严格递增数组 $ a $ 的元素,使其特征数尽可能大。如果有多个答案,输出其中任意一个。 **输入输出样例** - **输入样例 #1**: ``` 7 5 9 4 12 3 3 3 4 4 4 4 6 8 11 ``` - **输出样例 #1**: ``` 1 3 4 7 8 2 4 7 12 1 2 3 1 3 4 1 2 3 4 2 4 5 6 1 2 3 5 6 7 8 11 ```

加入题单

上一题 下一题 算法标签: