QOJ.ac

QOJ

Limite de temps : 2.0 s Limite de mémoire : 512 MB Points totaux : 100

#15810. 集合族

Statistiques

给定集合 $A = \{1, 2, \dots, n\}$ 以及由 $A$ 的子集构成的集合族 $L$,其中 $L$ 中的每个子集的大小均为 $k$。考虑以下过程:

  1. 等概率且独立地为 $A$ 中的每个元素分配权值 $1$ 或 $2$。
  2. 将 $L$ 中每个子集的权值计算为其所含元素的权值之和。
  3. 如果 $L$ 中恰好只有一个子集具有最小权值,则称该权值分配是好的(good)。

给定集合 $A = \{1, 2, \dots, n\}$ 和整数 $k$(表示 $L$ 中每个子集的大小)。你的任务是构造一个这样的集合族 $L$,使得好的权值分配的概率小于 $\frac{1}{100}$。

例如,当 $A = \{1, 2\}$,$L = \{\{1\}, \{2\}\}$ 时。分配方案 $\{1, 2\}$(即元素 1 权值为 1,元素 2 权值为 2)和 $\{2, 1\}$ 是好的;而 $\{1, 1\}$ 和 $\{2, 2\}$ 不是好的,因为此时两个子集的权值相等且均为最小。因此,好的分配方案的概率等于 $\frac{1}{2}$。

输入格式

输入只有一行,包含两个整数 $n, k$。

在样例 $n = 2, k = 1$ 中,任何格式正确的输出都将被判定为正确(OK)。请注意,对于该样例,不存在满足题目要求的集合族。

在实际测试数据中,$n = 14$,$2 \le k \le 12$,且保证存在解。

输出格式

第一行输出一个整数 $m$ ——— $L$ 中子集的数量。

接下来的 $m$ 行,每行包含一个子集的描述。第 $i$ 行包含 $k$ 个介于 $1$ 到 $n$ 之间且互不相同的整数,整数之间用空格隔开,表示该子集的元素。

输出中的所有子集必须互不相同。

样例

输入样例 1

2 1

输出样例 1

2
1
2

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.