#P14728. [Bulgarian2019春季赛]counter

[Bulgarian2019春季赛]counter

题目描述

图灵有一台机器。这台机器相当特别:它由一条无限长纸带组成,纸带被划分为许多格子,每个格子里写着一个符号。机器有一个读写头,它在任意时刻都位于纸带上的某个格子上方。

机器还有一个计数器,其值是一个非负整数。机器始终处于 KK 个状态之一(编号为 00 到 K−1K-1)。

机器按迭代方式运行:每一轮会执行一条由“当前状态”和“读写头当前所指符号”唯一确定的指令。

每条普通指令会按如下顺序执行四个动作:

  1. 在当前格子中写入某个符号(可以与原符号相同);
  2. 读写头向左移动一格、向右移动一格,或者停在原地;
  3. 机器转移到某个状态,或者保持原状态;
  4. 计数器加一,或者保持不变。

此外还有一种停止指令,会让机器终止运行。执行停止指令时,计数器同样可以选择加一,也可以不变。

纸带上可能出现的符号只有 0 和 1。另外,恰有一个格子中初始写着符号 S。

在机器启动时:

  • 机器状态为 00;
  • 计数器值为 00;
  • 纸带上除一个格子写有 S 外,其余格子全为 0;
  • 读写头初始正位于写有 S 的那个格子上。

从那以后,机器只能在纸带上写 0 或 1。唯一的例外是:当读写头位于 S 所在格时,它也可以再次写入 S,从而保持该符号不变;当然,它也可以写 0 或 1,这样 S 就会从纸带上消失。

图灵想利用这台机器来制作一个计数器。他希望为机器设计一组指令,使得机器最终一定会停止运行,并且在停止时,计数器的值恰好等于 NN。

他需要对很多不同的 NN 都完成这件事,因此不想每次都手工写指令。于是他想写一个普通程序,根据输入的 NN 自动生成这组指令。不过在他的时代还没有这样的计算机,因此他向你求助。

请编写程序 counter:给定 NN,输出一组满足要求的机器指令。你可以自由选择状态数 KK,但由于硬件限制,必须满足 K≤20K \le 20。

指令必须恰好为每一个 (符号, 状态) 对给出一条,并按如下顺序输出:

$$(S,0),(S,1),\dots,(S,K-1),(0,0),(0,1),\dots,(0,K-1),(1,0),(1,1),\dots,(1,K-1)$$

指令格式说明

普通指令的格式为:

M(C) Symbol State

其中:

  • M 表示移动方向:L 表示向左,S 表示停留,R 表示向右;
  • C 表示计数器加一;
  • Symbol 为 0、1 或 S 之一,表示第一步要写入当前格子的符号;
  • State 是一个从 00 到 K−1K-1 的整数,表示执行后转移到的状态。

停止指令的格式为:

H(C)

其中 C 的含义与上面相同。

注意:上面写法中的圆括号不属于实际语法,它只表示 C 是否出现是可选的。只有当指令中真的写出 C 时,计数器才会加一。请参考样例。

输入格式

输入一个非负整数 NN。

输出格式

第一行输出一个整数 KK,表示你使用的状态数。

接下来输出 3×K3\times K 行,依次给出上述顺序中每个 (符号, 状态) 对应的指令。

数据范围

  • 1≤K≤201 \le K \le 20
  • 1≤N≤22 000 0001 \le N \le 22\,000\,000
  • 机器必须在 30 000 00030\,000\,000 次迭代以内停止

子任务与评分

子任务 分值 累计分 限制
1 10 N≤20N \le 20
2 5 15 N≤60N \le 60
3 10 25 N≤120N \le 120
4 5 30 N≤399N \le 399
5 10 40 N≤500N \le 500
6 5 45 N≤1000N \le 1000
7 50 N≤5000N \le 5000
8 10 60 N≤130000N \le 130000
9 5 65 N≤260000N \le 260000
10 70 N≤600000N \le 600000
11 75 N≤1000000N \le 1000000
12 80 N≤3000000N \le 3000000
13 85 N≤5000000N \le 5000000
14 90 N≤10000000N \le 10000000
15 95 N≤20000000N \le 20000000
16 100 N≤22000000N \le 22000000

只有通过某一子任务中的全部测试点,才能获得该子任务的分数。

本地测试

题目提供了解释器 interpreter.cpp,其行为与评测系统中使用的解释器等价(只是输出内容略有不同),可用于本地测试你的程序。你可以对它进行任意修改。

样例

输入

3

输出

2
RC S 0
HC
S 1 1
L 1 0
R 1 0
LC 0 1

说明

下面给出该样例的一种执行过程。为方便说明,以下用方括号表示读写头当前位置:

纸带与读写头 状态 计数器 执行的指令
... 0 0 [S] 0 0 ... 0 0 RC S 0
... 0 0 S [0] 0 ... 1 S 1 1
... 0 0 S [1] 0 ... 1 LC 0 1
... 0 0 [S] 0 0 ... 2 HC
— — 3 —

指令 L 1 0 和 R 1 0 在这个样例中一次也不会被执行。