#P17910. Leo
Leo
题目描述
三色逻辑中,一个信号有四种可能的状态:R(红色)、G(绿色)、B(蓝色)和 *(透明)。前三种是有色状态,透明是唯一的无色状态。
你需要设计一台名为 Leo 的计算设备。它是一张有向无环图,每个节点保存一个上述状态。给定输入规模 ,设备的结构必须满足:
- 节点 是输入节点,没有前驱。它们的状态由设备的输入给定。
- 节点 是内部节点。每个内部节点有两个前驱,两个前驱可以是同一个节点,但它们的编号都必须严格小于当前节点的编号。
- 节点 是设备唯一的输出节点,它的状态就是设备的输出。
- 内部节点数满足 。
每个内部节点必须是以下两类逻辑门之一,其状态由两个前驱的状态确定。
三色 AND 门
输出时用字符 & 表示。
如果两个前驱的状态相同,则输出这一状态;否则输出 *。完整规则如下,行和列分别表示两个前驱的状态:
| AND | R |
G |
B |
* |
|---|---|---|---|---|
R |
* |
* |
* |
|
G |
* |
G |
||
B |
* |
B |
||
* |
* |
|||
三色 OR 门
输出时用字符 | 表示。
- 如果两个前驱的状态相同,则输出这一状态。
- 如果恰有一个前驱为
*,则输出另一个前驱的颜色。 - 如果两个前驱都是有色状态,且颜色不同,则输出剩下的第三种颜色。
完整规则如下:
| OR | R |
G |
B |
* |
|---|---|---|---|---|
R |
B |
G |
R |
|
G |
B |
G |
R |
G |
B |
G |
R |
B |
B |
* |
R |
G |
* |
|
设备需要实现以下功能。
保证给输入节点赋予的状态中,R、G、B 都至少出现一次,而 * 可以出现任意次,包括零次。从节点 扫描到节点 ,忽略所有 *,设备必须输出第三种首次遇到的颜色。
等价地,分别记录 R、G、B 第一次出现的位置,设备应输出这三个位置中最大者对应的颜色。例如,输入为 RGRB 时,三种颜色首次出现的顺序为 R、G、B,因此输出应为 B。
你的程序只会收到规模 ,不会收到具体的颜色序列。你需要输出一套固定的设备结构,使它对于每一种满足上述保证的输入状态序列都能正确工作。
输入格式
输入仅有一行,包含一个整数 ,表示设备的输入节点数。
输出格式
第一行输出一个整数 ,表示你设计的内部节点数,必须满足 。
接下来输出 行。第 行包含一个字符 和两个整数 ,用于描述内部节点 :
- 必须是字符
&或|,分别表示三色 AND 门或三色 OR 门。 - 是该节点的两个前驱编号,满足 。
- 允许 。
如果存在多种合法设计,可以输出任意一种,不需要最小化 。
数据范围
。本题只有一组数据。
原题评测说明
原题评测程序会为每个测试点生成 组合法的设备输入,并依次送入你构造的设备。如果设备对这些输入的输出都符合要求,则通过该测试点。
这里的设备输入是输入节点的状态序列,由评测程序提供给所构造的设备;你的程序本身仍然只读取整数 ,并输出设备结构。
样例输入
4
样例输出
5
| 1 2
& 3 5
| 4 6
& 4 7
| 6 8
样例说明
该方案有四个输入节点和五个内部节点,输出节点为节点 。对于任意合法的四个输入状态,这套设备都能得到正确答案。
以下给出原题两个示例中的逐节点计算:
| 节点 | 类型 | 前驱 | 输入为 RGRB 时的状态 |
输入为 BRG* 时的状态 |
|---|---|---|---|---|
| 5 | OR | 1、2 | B |
G |
| 6 | AND | 3、5 | * |
|
| 7 | OR | 4、6 | B |
|
| 8 | AND | 4、7 | * |
|
| 9 | OR | 6、8 | G |
因此,输入为 RGRB 时输出 B;输入为 BRG* 时输出 G。