#L4243. 「NordicOI 2021」Amazing Whispers
「NordicOI 2021」Amazing Whispers
题目描述
译自 NordicOI 2021 Day2 T3「Amazing Whispers」
一群朋友想玩一个神奇的传话游戏,这个游戏的规则如下:
你有 个人,分成 组,每组有 个人。
一个秘密短语被分成 个不同的信息,每个组 的成员会收到一个不同的信息。
这些信息会从组 传递到组 ,再从组 传递到组 ,以此类推,直到最终从组 传递到组 。每条信息都会被传递,但每个人只能听到一条信息。
为了让观察者更难追踪信息,每个组 的人会假装对组 的最多 个人传话。实际上,只有其中一个人会真正听到信息,其他人只是被假装传话。这样,观察者就无法知道组 中的哪个人真正收到了信息。组 的人已经安排好,让组 的每个人都能听到一条信息。
当所有信息到达组 后,它们会被大声读出来。结果发现,所有信息都成功传递,除了其中一条被替换成了粗鲁的话。 号人最初持有丢失的信息,而 号人是唯一一个读出粗鲁话的人。你不知道在传递过程中哪个阶段发生了替换。谁可能是这个恶作剧的罪魁祸首?
你不知道信息是如何传递的。你只知道那些假装传话的人的配对情况。
输入格式
第一行包含四个整数 , , , ,如题目所述。
人们的编号从 到 ,编号为 的人属于组 。( 表示不大于 的最大整数。)
接下来是 行。第 行描述第 个人假装对谁传话。
每行以一个整数 开头,表示第 个人假装对 个人传话。接下来是 个整数 ,指定那些人是谁。这些人总是属于第 个人所在组的下一组,这些数字满足 $\left \lfloor{R_{i,j}/N}\right \rfloor = \left \lfloor{i/N}\right \rfloor + 1$。
输出格式
输出的第一行应包含一个整数 ,表示可能是恶作剧罪魁祸首的人数。
接下来的 行应列出这些人,每行一个人,按编号升序排列。
样例 1
输入
2 3 1 5
1 3
1 2
2 5 4
2 4 5
输出
3
1
2
5
样例 2
输入
3 3 0 6
1 4
1 5
1 3
1 7
2 6 7
1 8
输出
3
0
4
6
数据范围与提示
对于所有输入数据,满足:
- 所有 的总和不超过
- 输入描述了一种有效的传递方式
详细子任务附加限制及分值如下表所示。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 18 | |
| 2 | 16 | , |
| 3 | 19 | |
| 4 | 47 | 无附加限制 |