开始 2024-10-04 19:27:29

1005CSP模拟赛

结束 2024-11-05 12:00:00
Contest is over.
当前 2024-12-22 22:12:12

D. 拉群

描述

n 个人,编号从 1\sim n。需要建立若干个聊天群,每个聊天群的人数上限为 m。需要保证对于任意两个人 x,y,满足如下要求:

  • 至少有一个群既有 x 又有 y
  • 至少有一个群只有 x 没有 y
  • 至少有一个群只有 y 没有 x

假设最多只能建立 k 个群,请你给出一个满足要求的方案。

输入

一行,两个整数:n,m,k

输出

第一行为建立群的数量(必须小于等于 k)。

接下来输出 n 行,每行都对应你的方案的一个群。每行首先输出一个正整数(必须小于等于 m),表示当前聊天群人数,然后输出这么多个人的编号(必须在 1\sim n 的范围内),即当前群内成员。

如果有多种方案,任意输出一种即可。

样例

输入

5 5 10

输出

8
4 1 2 3 4 
4 1 2 3 5
4 2 3 4 5
1 1
3 2 1 4
5 1 2 3 4 5
4 3 1 4 5
1 5

提示

样例解释:这里给了一种分法,分成了 8 个群,保证了满足题目的三个要求。注意,这个样例提示了我们,可以有只有一个人的群。

数据规模与约定

对于 100\% 的数据,2 \le n \le 102\le m\le n,保证至少有一个解。

  • 子任务 1(10 分):保证 n=2,k=10
  • 子任务 2(20 分):保证 m=n,k=n+1
  • 子任务 3(30 分):保证 m=2,k=n^2
  • 子任务 4(40 分):保证 k=\lceil\frac{n\times (n-1)}{m-1}\rceil

Submit

登录

注册
时间限制 1 秒
内存限制 128 MB
提交