#P17910. Leo

Leo

题目描述

三色逻辑中,一个信号有四种可能的状态:R(红色)、G(绿色)、B(蓝色)和 *(透明)。前三种是有色状态,透明是唯一的无色状态。

你需要设计一台名为 Leo 的计算设备。它是一张有向无环图,每个节点保存一个上述状态。给定输入规模 nn,设备的结构必须满足:

  • 节点 1,2,…,n1,2,\ldots,n 是输入节点,没有前驱。它们的状态由设备的输入给定。
  • 节点 n+1,n+2,…,n+mn+1,n+2,\ldots,n+m 是内部节点。每个内部节点有两个前驱,两个前驱可以是同一个节点,但它们的编号都必须严格小于当前节点的编号。
  • 节点 n+mn+m 是设备唯一的输出节点,它的状态就是设备的输出。
  • 内部节点数满足 1≤m≤6n1\le m\le6n。

每个内部节点必须是以下两类逻辑门之一,其状态由两个前驱的状态确定。

三色 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 都至少出现一次,而 * 可以出现任意次,包括零次。从节点 11 扫描到节点 nn,忽略所有 *,设备必须输出第三种首次遇到的颜色。

等价地,分别记录 R、G、B 第一次出现的位置,设备应输出这三个位置中最大者对应的颜色。例如,输入为 RGRB 时,三种颜色首次出现的顺序为 R、G、B,因此输出应为 B。

你的程序只会收到规模 nn,不会收到具体的颜色序列。你需要输出一套固定的设备结构,使它对于每一种满足上述保证的输入状态序列都能正确工作。

输入格式

输入仅有一行,包含一个整数 nn,表示设备的输入节点数。

输出格式

第一行输出一个整数 mm,表示你设计的内部节点数,必须满足 1≤m≤6n1\le m\le6n。

接下来输出 mm 行。第 ii 行包含一个字符 tit_i 和两个整数 ui,viu_i,v_i,用于描述内部节点 n+in+i:

  • tit_i 必须是字符 & 或 |,分别表示三色 AND 门或三色 OR 门。
  • ui,viu_i,v_i 是该节点的两个前驱编号,满足 1≤ui,vi<n+i1\le u_i,v_i<n+i。
  • 允许 ui=viu_i=v_i。

如果存在多种合法设计,可以输出任意一种,不需要最小化 mm。

数据范围

3≤n≤1053\le n\le10^5。本题只有一组数据。

原题评测说明

原题评测程序会为每个测试点生成 ⌊107n⌋\left\lfloor\dfrac{10^7}{n}\right\rfloor 组合法的设备输入,并依次送入你构造的设备。如果设备对这些输入的输出都符合要求,则通过该测试点。

这里的设备输入是输入节点的状态序列,由评测程序提供给所构造的设备;你的程序本身仍然只读取整数 nn,并输出设备结构。

样例输入

4

样例输出

5
| 1 2
& 3 5
| 4 6
& 4 7
| 6 8

样例说明

该方案有四个输入节点和五个内部节点,输出节点为节点 99。对于任意合法的四个输入状态,这套设备都能得到正确答案。

以下给出原题两个示例中的逐节点计算:

节点 类型 前驱 输入为 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。