QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100

# 8357. 自动机

Statistics

小 D 最近学了有限自动机上用 LCC 维护的有限群分治 DFT,并得意的到处显摆。

大 D 看不下去了,给小 D 出了一个难题,对于字符集大小为 $2$ 的非确定性有限自动机 $G=(V,E_0,E_1,v_0,F)$,定义 $L(G)$ 为最短的不可被 $G$ 接受的 01 串长度,如果不存在则为 $0$,大 D 限制了 $|V|\leq n$,你需要造一个自动机 $G$ 使得 $L(G)$ 尽可能大。

这里给出自动机的粗略定义:

  • $V$ 表示点集。
  • $E_0,E_1$ 分别是两个定义在 $V$ 上的有向边集。
  • $v_0\in V$ 表示起始点。
  • $F\subset V$ 表示接受点集。
  • 自动机 $G$ 接受长为 $k$ 的 01 串 $S$ 当且仅当存在一个点序列 $v_0,v_1,\cdots,v_k$ 满足 $v_k\in F$ 且 $(v_{i-1},v_i)\in E_{S_i}$。

输入格式

一行一个整数 $n$。

输出格式

输出自动机 $G$。这里要求 $V=\{0,1,\cdots,n-1\},v_0=0$。

首先输出 $E_0$,形如:

第一行一个整数 $|E_0|\in [0, 1000]$。

接下来 $|E_0|$ 行每行两个整数 $u,v$ 表示一条边 $(u,v)$。

接下来以相同格式输出 $E_1$。

接下来输出 $F$,格式如下:

第一行一个整数 $|F|$。

接下来 $|F|$ 个整数表示 $F$ 内的元素。

样例

input

3


output

2
0 0
2 2
4
0 1
1 0
0 2
2 1
3
0 1 2


explanation

最短的不可被接受的字符串是 1010

数据范围与提示

本题只有两组数据:

第一组数据 $n=6$,你的得分为 $50\max(0, \min(1, \frac{L(G)-11}{10}))$。

第二组数据 $n=20$,你的得分为 $50\max(0, \min(1, \frac{\sqrt{L(G)}}{20}))$。