Clique Partition
Description
You are given two integers, $n$ and $k$. There is a graph on $n$ vertices, numbered from $1$ to $n$, which initially has no edges.
You have to assign each vertex an integer; let $a_i$ be the integer on the vertex $i$. All $a_i$ should be distinct integers from $1$ to $n$.
After assigning integers, for every pair of vertices $(i, j)$, you add an edge between them if $|i - j| + |a_i - a_j| \le k$.
Your goal is to create a graph which can be partitioned into the minimum possible (for the given values of $n$ and $k$) number of cliques. Each vertex of the graph should belong to exactly one clique. Recall that a clique is a set of vertices such that every pair of vertices in it are connected with an edge.
Since BledDest hasn't really brushed his programming skills up, he can't solve the problem "given a graph, partition it into the minimum number of cliques". So we also ask you to print the partition itself.
deepl翻译
给你两个整数 和 。在 个顶点上有一个图，编号从 到 ，最初没有边。
您必须为每个顶点分配一个整数；让 成为顶点 上的整数。所有的 都应该是从 到 的不同整数。
分配整数后，对于每一对顶点 ，如果有 则在它们之间添加一条边。
您的目标是创建一个可以分割成尽可能少的（对于给定的 和 值）小群的图。图中的每个顶点都应属于一个小群。回想一下，一个小群是一个顶点集合，其中的每一对顶点都有一条边相连。
由于 BledDest 还没有真正掌握编程技巧，所以他无法解决 "给定一个图，将其划分为最小数目的小群 "这一问题。因此，我们还要求您打印出分区本身。
Input
The first line contains one integer $t$ ($1 \le t \le 1600$) — the number of test cases.
Each test case consists of one line containing two integers $n$ and $k$ ($2 \le n \le 40$; $1 \le k \le 2n$).
Output
For each test case, print three lines:
- the first line should contain $n$ distinct integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — the values you assign to the vertices;
- the second line should contain one integer $q$ ($1 \le q \le n$) — the number of cliques you partition the graph into;
- the third line should contain $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le q$) — the partition of the graph into cliques. Where two vertices $u$ and $v$ are in the same clique if $c_u = c_v$.
If there are multiple answers, print any of them.
3
2 3
5 4
8 16
2 1
1
1 1
3 1 5 2 4
2
1 1 2 1 2
1 2 3 4 5 6 7 8
1
1 1 1 1 1 1 1 1
相关
在下列比赛中: