#P2943. [Poi2000]三臂起重机

    ID: 2063 传统题 1000ms 128MiB 尝试: 13 已通过: 5 难度: 5 上传者: 标签>CF1700普及+/提高-序列构造极端元素优先处理对称性分析

[Poi2000]三臂起重机

题目描述

一架三臂起重机正在把集装箱放进货车车箱。车箱由 11 至 nn 编号,每节车箱上仅能放一个集装箱。一次移动,起重机能把三个集装箱从仓库里拿出并放进车箱 ii、i+pi+p、i+p+qi+p+q 或 ii、i+qi+q、i+p+qi+p+q( pp、qq 为大于等于 11 的常数)。起重机必须放满货车的前 nn 节车箱(货车有 n+p+qn+p+q 节车箱)。放置的方案由一系列说明组成,每条说明指 示起重机的一次移动,用三个整数 (x,y,z)(x,y,z) 表示这次接受集装箱的车箱的编号,其中 1≤x<y<z≤n+p+q1\le x<y<z\le n+p+q。如果在说明执行后,货车前 nn 节车箱有且仅有一个箱子,则该方案是正确的。

你需要编写一个程序,生成一个正确的放置方案。

输入格式

第一行仅包括三个正整数,用空格分开。它们是起重机恰当的参数 p,qp,q,需要装满的车箱数 nn。

输出格式

第一行仅有一个整数 mm,表示生成方案中说明的条数。

接下来 mm 行,每行有三个整数 x,y,zx,y,z,用空格分开,1≤x<y<z≤n+p+q1\le x<y<z\le n+p+q,x≤nx\le n,y∈{x+p,x+q}y\in\{x+p,x+q\},z=x+p+qz=x+p+q,表示一次移动中接受箱子的车箱的编号。

2 3 10
4
1 3 6
2 4 7
5 8 10
9 11 14

数据规模与约定

对于 100%100\% 的数据,1≤n≤3×1051\le n\le 3\times 10^5,2≤p+q≤6×1042\le p+q\le 6\times 10^4。