#P8545. 「Wdoi-2」不败的无尽兵团
「Wdoi-2」不败的无尽兵团
题目背景
畜生界是一个被动物灵所占据的,究极的弱肉强食的空间,也是个被几个组织所支配的世界——劲牙组、鬼杰组、刚欲同盟……
在这些动物灵其中也有一些灵长类动物的灵,也就是人类灵,它们弱小但又手脚灵活,作为完完全全的奴隶苟存在灵长园这一娱乐设施中。
但人类的灵也是有信仰的,它们向神明祈求,神也回应了人类的祈求,向人类给予了信仰的偶像。然而,人类灵原本只是皈依于存在于偶像背后的神性,却逐渐开始信仰起偶像本身来。结果,自然而然地,偶像开始支配人类,使得灵长园变成一个凶恶的失控组织。
畜生界也因为灵长园的暴动变得混乱,为了打倒偶像,鬼杰组希望能够卷入地上的人类,借用人类之手毁灭灵长园。动物灵们也就来到了地上,也就是幻想乡,带领灵梦一行人一同前往地狱。
题目描述
简要题意
对于正整数 ( 为 或 ), 的 个子集 为好的,如果对于 的每一个三元子集 ,都存在 恰好 一个 使得 为 的子集。构造一个好的子集族使得 尽量小(不超过题目给定的评分参数)。
原始题意
一路进入畜生界的灵梦,遭遇到了埴轮兵团的首长,杖刀偶磨弓的阻拦。
埴轮兵团由 个战士组成,它们编号为 。战士数量为 或者 。作为一个兵团,要做到最好的进攻与防守,埴轮之间存在 组配合关系 ,每组关系包含若干个不同(但不少于 个)的埴轮战士,但不同组的关系中包含的埴轮战士可以重复。
但是灵梦并不事先知道这些配合关系,而且由于埴轮兵团配合默契,灵梦难以强行击败它们。在动物灵的帮助之下,灵梦发现,这些埴轮满足如下特点:从埴轮兵团中任意选出 个埴轮,都存在 恰好 一个 ,使得这三个埴轮是 的一个子集。在满足这个特点的基础之上,由于磨弓的精力有限,无法同时维护太多组配合关系。因此, 是一个大于等于 的一个正整数,且其小于等于 。
现在灵梦告诉了你埴轮兵团的总人数,请你告诉她一种可能的埴轮兵团配合的情况,帮助她打败杖刀偶磨弓,进入灵长园。
输入格式
第一行有一个正整数 ,含义如题意所示。保证 或者 。
输出格式
第一行输出一个正整数 ,表示你构造的方案使用的集合的总个数。应当满足 。
接下来 行,每行输出若干个整数。第一个整数 表示你构造的 的大小,应当满足 。接下来 个整数描述 内的元素,中间用空格隔开。
4
4
3 1 2 3
3 1 2 4
3 1 3 4
3 2 3 4
5
7
4 1 2 3 4
3 1 2 5
3 1 3 5
3 1 4 5
3 2 3 5
3 2 4 5
3 3 4 5
提示
样例 1 解释
样例仅供理解题意参考。实际数据中, 只会为 或 。
由于 ,因此结果不能为 ;又因为 时 无用,于是唯一的方案就是列出 的所有三元子集 。
数据范围及约定
$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \textbf{Subtask} & \bm{n=} & \bm{m_{\text{ans}}=} & \textbf{分值} \cr\hline 1 & 529 & 1.25\times 10^4 & 75 \cr\hline 2 & 625 & 1.60\times 10^4 & 25 \cr\hline \end{array}$$如果你输出的方案不合法,那么你将不能获得该测试点的得分。
当你构造的解符合题设,并且 的值不超过 ,你才能获得该测试点的分值。