#P4790. [CERC2016]Dancing Disks

    ID: 3907 传统题 3000ms 512MiB 尝试: 33 已通过: 18 难度: 9 上传者: 标签>难度分类提高+/省选-构造与建模递归构造动态规划网格 DP不变量分析数据结构栈CF2600

[CERC2016]Dancing Disks

[CERC2016] 舞动的盘子 Dancing Disks

题目描述

Luka 熟悉汉诺塔,发明了一种使用盘子和柱子的游戏。有 nn 个大小互不相同的盘子,按大小从小到大编号为 11 至 nn。3636 根柱子排成 66 行 66 列,行号从上到下、列号从左到右均为 11 至 66。

示例操作把左侧柱子顶部的一叠盘子整体移到右侧

初始时,所有盘子叠在左上角 (1,1)(1,1) 的柱子上。每一步任选一根柱子,从顶部取下一叠盘子,至少取一个,再把整叠盘子原顺序放在其正下方或正右方相邻柱子的顶部。

目标是把全部盘子移到右下角 (6,6)(6,6) 的柱子上,并使它们从顶到底按大小递增。保证存在解,给出任意一种合法操作序列。

输入格式

第一行一个整数 nn。第二行 nn 个整数 d1,…,dnd_1,\ldots,d_n,按从底到顶的顺序给出左上角柱子上的盘子编号。这 nn 个编号互不相同,且都在 [1,n][1,n] 内。

输出格式

每步输出一行 r c p k。r,cr,c 是取盘子的柱子的行、列编号,均在 [1,6][1,6] 内。pp 为 D 或 R,分别表示向下或向右移动到相邻柱子。kk 为正整数,表示移动该柱顶部的盘子数。

按执行顺序逐行输出所有步骤。所有步骤都必须合法且最终达到目标。

数据范围

1≤n≤400001\le n\le40000。

样例 #1

样例输入 #1

6
1 6 5 4 3 2

样例输出 #1

1 1 D 6
2 1 D 6
3 1 D 6
4 1 D 6
5 1 D 6
6 1 R 6
6 2 R 6
6 3 R 6
6 4 R 6
6 5 R 5
6 5 R 1

样例说明

前九步把整叠盘子移到 (6,5)(6,5),盘子的顺序未改变。第十步把顶部五个盘子整体移到目标柱,这五个盘子从底到顶为 6,5,4,3,26,5,4,3,2。最后再放上编号为 11 的盘子。