← 返回题目列表

AtCoder · ttpc2022_o

O. 并行处理

中文机器翻译题面 查看原题

配点 : 500 点

简单的问题描述

神秘的幺半群 (M, \oplus) 以及计算它的 CPU 4 件。

整数 N ,所以M 栏 A = (A_1, A_2, …, A_N) 减去 A 的累积 \oplus 该值应乘以 4 请并行计算。
此时,请最小化操作次数。

严格的问题描述

整数 N 被给予。请创建以下(自有语言的)程序。在此过程中,请尽量减少指令数量。

程序规范

在此程序中,2004 变量 这是一台显示 A[1], A[2], …, A[2000], C_1, C_2, C_3, C_4 可以处理。每个变量可以拥有整数序列 1 个,A[i] (1 ≤ i ≤ 2000的初始值表示由 A[i] = (i) 。
( (i) 是 您也可以写 i 仅组成的整数序列。)

在程序执行结束时,必须满足以下条件。

  • i = 1, 2, …, N ,A[i] = (1, 2, …, i) 。

程序形式

程序的 1 行写着表示程序指令数量的整数 L 。
程序的 2 从行 4L+1 在线 L 条指令 4 行写一次。指令按从上到下顺序执行。

指令是 12 整数 给出了 c_1, a_1, b_1, c_2, a_2, b_2, c_3, a_3, b_3, c_4, a_4, b_4所写的各整数是 1 以上 2000 。
在各个命令中按以下顺序进行操作。

  1. C_1 至 该值是 \text{concat}(A[a_1], A[b_1]) 赋值为。
  2. C_2 至 该值是 \text{concat}(A[a_2], A[b_2]) 赋值为。
  3. C_3 至 该值是 \text{concat}(A[a_3], A[b_3]) 赋值为。
  4. C_4 至 该值是 \text{concat}(A[a_4], A[b_4]) 赋值为。
  5. A[c_1] 至 该值是 C_1 赋值为。
  6. A[c_2] 至 该值是 C_2 赋值为。
  7. A[c_3] 至 该值是 C_3 赋值为。
  8. A[c_4] 至 该值是 C_4 赋值为。

在这里,\text{concat}(x, y) 是指整数列 x, y 表示按此顺序连接的整数列。

制約

  • N 是一个整数
  • 2 ≤ N ≤ 10^3

部分点

  • 2 ≤ N ≤ 16 的数据集 给出 200 点。 如果您正确回答了所有满足
  • 17 ≤ N ≤ 10^3 的数据集 给出 300 点。 如果您正确回答了所有满足

入力

输入是按以下格式从标准输入给出的。

N

出力

命令数的最小值为 L 。

L
\text{op}_1
\text{op}_2
\vdots
\text{op}_L

\text{op}_i (1 ≤ i ≤ L) 是 i 表示第几次命令。\text{op}_i 按以下格式输出。

c_1 a_1 b_1
c_2 a_2 b_2
c_3 a_3 b_3
c_4 a_4 b_4

此处,每个整数是 1 以上 2000 。


入力例 1

2

出力例 1

1
2 1 2
2000 2000 2000
2000 2000 2000
2000 2000 2000

1 在第几次命令中,A[2] 是 您也可以写 (1, 2) 属于A[2000] 是 您也可以写 (2000, 2000) 。

在执行结束时 A[1] = (1), A[2] = (1, 2) 成为这样,因此这是满足规格的程序。


入力例 2

4

出力例 2

2
2 1 2
4 3 4
2000 2000 2000
2000 2000 2000
3 2 3
4 2 4
2000 2000 2000
2000 2000 2000

1 在第几次命令中,A[2] 是 您也可以写 (1, 2) 属于A[4] 是 您也可以写 (3, 4) 属于A[2000] 是 您也可以写 (2000, 2000) 。
2 在第几次命令中,A[3] 是 您也可以写 (1, 2, 3) 属于A[4] 是 您也可以写 (1, 2, 3, 4) 属于A[2000] 是 您也可以写 (2000, 2000, 2000, 2000) 。

在执行结束时 A[1] = (1), A[2] = (1, 2), A[3] = (1, 2, 3), A[4] = (1, 2, 3, 4) 成为这样,因此这是满足规格的程序。