AT_ttpc2022_o.Parallel Processing

简要问题描述

有一个神秘的幺半群 $(M, \oplus)$，并且有 $4$ 个可以执行该运算的 CPU。

给定一个整数 $N$，请你使用 $4$ 路并行计算 $M$ 的序列 $A = (A_1, A_2, \ldots, A_N)$ 的累积 $\oplus$，并使操作次数最小化。

严格问题描述

给定一个整数 $N$。请你按照以下（自定义语言的）规范编写程序，并且使指令数最小。

程序规范

本程序可以处理 $2004$ 个变量 $A[1], A[2], \ldots, A[2000], C_1, C_2, C_3, C_4$。每个变量都持有一个整数序列。其中 $A[i]$（$1 \leq i \leq 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. 将 $\text{concat}(A[a_1], A[b_1])$ 赋值给 $C_1$；
2. 将 $\text{concat}(A[a_2], A[b_2])$ 赋值给 $C_2$；
3. 将 $\text{concat}(A[a_3], A[b_3])$ 赋值给 $C_3$；
4. 将 $\text{concat}(A[a_4], A[b_4])$ 赋值给 $C_4$；
5. 将 $C_1$ 赋值给 $A[c_1]$；
6. 将 $C_2$ 赋值给 $A[c_2]$；
7. 将 $C_3$ 赋值给 $A[c_3]$；
8. 将 $C_4$ 赋值给 $A[c_4]$。

其中，$\text{concat}(x, y)$ 表示将整数序列 $x$、$y$ 依次连接而成的新整数序列。

输入通过标准输入给出，格式如下：

$N$

设指令数的最小值为 $L$，输出格式如下：

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

其中，$\text{op}_i$（$1 \leq i \leq L$）表示第 $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$ 之间。

部分分

• 对所有满足 $2 \leq N \leq 16$ 的数据集，答对可以获得 $200$ 分。
• 对所有满足 $17 \leq N \leq 10^3$ 的数据集，答对可以获得 $300$ 分。

样例解释 1

第 $1$ 条指令后，$A[2]$ 变为 $(1, 2)$，$A[2000]$ 变为 $(2000, 2000)$。

结束时 $A[1] = (1), A[2] = (1, 2)$，满足要求。

样例解释 2

第 $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)$，满足要求。

数据范围

• $N$ 为整数；
• $2 \leq N \leq 10^3$。

由 ChatGPT 5 翻译