这是一道提交答案题。你需要提交数据生成器。
K 主席为春季训练营的参与者准备了一个游戏。
训练营中共有
- K 主席选择一名参与者作为父节点(parent),其余参与者成为子节点(children)。但父节点的身份不会向参与者公开。
- K 主席在父节点的白板上写下字母
,在所有子节点的白板上写下字母 。 - 每位参与者阅读自己白板上的字母。然后,按照预先定义好的策略,执行以下回合制流程(共
个回合):- 每位参与者擦除白板上的字母,并写下
或 ,然后将白板提交给 K 主席。 - 对于每个参与者
( ):- 参与者
选择一个参与者 ( )并将编号 告知 K 主席。 - K 主席将参与者
的白板展示给参与者 ,参与者 读取上面的字母。参与者可以选择自己作为 。
- 参与者
- 每位参与者擦除白板上的字母,并写下
- 经过
个回合后,每位参与者必须猜测谁是父节点。
游戏的目标是预先制定一个策略,使得无论谁被选为父节点,所有参与者都能在此流程结束时正确识别父节点。
更小的
一个策略由以下两部分组成:
- 一个非负整数
,表示回合数; - 一组规则,用于确定每个参与者的行为。规则如下:
- 对于参与者
( ),在第 个回合开始时( ),若其已读取的字母序列为 ,则仅基于这些信息( , , ),必须确定:- 在该回合要写入白板的字母;
- 在该回合选择观察的参与者编号。
- 对于参与者
( ),在第 个回合结束后,若其已读取的字母序列为 ,则仅基于这些信息( , , ),必须推断出父节点的编号。
- 对于参与者
请设计一个允许所有参与者正确识别父节点的策略(无论父节点是谁)。然后,针对每个可能的父节点选择(
输入格式
一行一个正整数
输出格式
输出格式如下:
其中,
1. 首先输出整数
2. 对于每个参与者
- 字符
( 或 ),表示该参与者在第 个回合写入白板的字母。 - 参与者编号
,表示该参与者在第 个回合选择观察的对象。
这些值需按回合顺序(
样例一
input
3
output
3 1 T 1 T 2 T 3 F 1 F 2 F 3 F 1 F 2 F 3 2 F 1 F 2 F 3 T 1 T 2 T 3 F 1 F 2 F 3 3 F 1 F 2 F 3 F 1 F 2 F 3 T 1 T 2 T 3
explanation
样例中,参与者的策略如下:
- 令
。 - 在每回合
( )中:- 参与者
若其为父节点则写入 ,若为子节点则写入 (根据初始步骤看到的字符,他们知道自己是否为父节点)。
- 参与者
- 在每回合
( )中:- 参与者
观察参与者 ,无论其当前已读取的字母序列如何。
- 参与者
- 经过
个回合后,每位参与者将恰好读取过包括自己在内的所有参与者的白板各一次。每位参与者将选择白板上出现过 的参与者编号作为父节点。
该策略确保所有人正确识别父节点,达成游戏目标。由于此策略在任何父节点选择下均满足游戏要求,因此输出被视为正确。
注意:样例不在实际测试数据中,因其不满足题目给定的约束条件。
数据范围
更为具体地说:
- 测试点
中, 。 - 测试点
中, 。 - 测试点
中, 。
计分方式
当且仅当输出符合以下条件时,才被视为正确:该输出是通过参与者遵循一个有效策略(确保所有参与者都能正确识别父节点)所产生的结果。具体而言,必须满足以下两个条件:
1. 对于任意参与者
2. 对于任意参与者
该题的得分为三个测试点的得分之和。
若输出不正确(例如格式错误或未遵循有效策略),则该测试点得
否则,若输出正确,则按以下标准计算得分:
测试点编号 | 计分方式 | 满分 | |
---|---|---|---|