#2189. 自动机

自动机

自动机

题目描述

标题: 自动机 - Problem - QOJ.ac

#8357. 自动机

Statistics

The problem was used in the following contests:

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

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

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

  • V 表示点集。
  • E0,E1 分别是两个定义在 V 上的有向边集。
  • v0∈V 表示起始点。
  • F⊂V 表示接受点集。
  • 自动机 G 接受长为 k 的 01 串 S 当且仅当存在一个点序列 v0,v1,⋯,vk 满足 vk∈F 且 (vi−1,vi)∈ESi。

输入格式

一行一个整数 n。

输出格式

输出自动机 G。这里要求 V={0,1,⋯,n−1},v0=0。

首先输出 E0,形如:

第一行一个整数 |E0|∈[0,1000]。

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

接下来以相同格式输出 E1。

接下来输出 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,你的得分为 50max(0,min(1,L(G)−1110))。

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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