由于某些原因本题仅支持 C++, C++11 语言的提交。
工程师 Christopher 在开发一款新的计算机处理器。
这个处理器可以访问
对所有的比特序列
该处理器有
:将寄存器 中的比特数组拷贝到寄存器 。对所有的 ( ),设置 。 :设置寄存器 等于 ,这里 是某个 个比特的数组。对于所有的 ( ),设置 。 :取寄存器 和 的按位与,并将结果存到寄存器 中。对于所有的 ( ),如果 和 同时为 则设置 ,否则设置 。 :取寄存器 和 的按位或,并将结果存到寄存器 中。对于所有的 ( ),如果 和 至少有一个为 则设置 ,否则设置 。 :取寄存器 和 的按位异或,并将结果存到寄存器 中。对于所有的 ( ),如果 和 恰好有一个为 则设置 ,否则设置 。 :取寄存器 的按位非,并将结果存到寄存器 中。对于所有的 ( ),设置 。 :左移寄存器 中的所有比特 位,并将结果存到寄存器 中。将寄存器 中的比特左移 位的结果,是一个包含 个比特的数组 。对于所有的 ( ),如果 则 ,否则 。对所有的 ( ),设置 。 :右移寄存器 中的所有比特 位,并将结果存到寄存器 中。将寄存器 中的比特右移 位的结果,是一个包含 个比特的数组 。对于所有的 ( ),如果 则 ,否则 。对所有的 ( ),设置 。 :将寄存器 和 中的整数值加起来,并将结果存到寄存器 中。加法是在模 下做的。正式一些来说,设 是操作前存在寄存器 中的整数值,而 是操作前存在寄存器 中的整数值。设 为操作后存在寄存器 中的整数值。如果 ,设置 中的比特使得 。否则,设置 中的比特使得 。
Christopher 希望你用这个新处理器解决两种任务。任务的类型用整数
程序的输入包括
执行某个程序就是按序执行其所包含的指令。在最后一条指令执行完毕后,程序的输出将根据寄存器
第一个任务(
)是要找出输入整数 中的最小值。 具体来说, 必须是 中的最小值。 的值可以是任意的。第二个任务(
)是要将输入整数 进行非降序排序。具体来说,对于所有的 ( ), 应当等于 中第 小的整数(也就是说, 是输入整数中的最小整数)。
请帮 Christopher 写一下解决这些任务的程序。每个程序至多只能包含
实现细节
你必须引用 registers.h
头文件。
你要实现如下函数:
void construct_instructions(int s, int n, int k, int q)
:任务类型。 :输入中的整数的数量。 :输入中的每个整数的比特数。 :允许的最大的指令数。- 该函数将被恰好调用一次,并应当为所要解决的任务创建一个指令序列。
该函数应当调用以下函数中的一或多个,以创建指令序列:
void append_move(int t, int y)
void append_store(int t, bool[] v)
void append_and(int t, int x, int y)
void append_or(int t, int x, int y)
void append_xor(int t, int x, int y)
void append_not(int t, int x)
void append_left(int t, int x, int p)
void append_right(int t, int x, int p)
void append_add(int t, int x, int y)
- 每个函数分别往程序追加一条
、 、 、 、 、 、 、 或 指令。 - 对于所有相关的指令,
、 、 必须至少为 且至多为 。 - 对于所有相关的指令,
、 、 不必是两两之间不同的。 - 对于指令
left
和right
, 必须至少为 且至多为 。 - 对于指令
store
, 的长度必须为 。
你还可以调用以下函数,以帮助测试你的答案:
void append_print(int t)
- 在评测你的答案时,对该函数的所有调用都将被忽略。
- 在评测程序示例中,该函数将往程序追加一个
操作。 - 当评测程序示例在执行某个程序过程中遇到一个
操作时,它会打印出由寄存器 中前 比特构成的 个 -比特整数(细节可参见“评测程序示例”部分)。 必须满足 。- 对该函数的任何调用,都不会算到你所创建的指令的数量里面。
在追加最后一条指令之后,construct_instructions
应当返回。随后你创建的程序将在一定数量的测试用例上评测,其中每个测试用例给出的输入数据为
- 如果
, 应当为 中的最小值。 - 如果
,对所有 ( )来说, 应当是 中第 小的整数。
在评测你的答案时,可能会给出下面的错误信息之一:
Invalid index
:在调用某些函数时的参数 、 或 所给出的寄存器下标是不正确的(可能是负数)。Value to store is not b bits long
:提供给append_store
的 的长度不等于 。Invalid shift value
:提供给append_left
或append_right
的 的值不在 和 之间(包括 和 )。Too many instructions
:你的函数试图追加超过 条指令。
评测程序示例
评测程序示例按以下格式读取输入:
- 第
行:
接下来还有若干行,每行描述一个单独的测试用例。每个测试用例将以如下格式给出:
这样,就描述出了一个包含
评测程序示例首先调用 construct_instructions(s, n, k, q)
。如果该调用违反了在程序说明中的某些限制,评测程序示例将打印出在“实现细节”部分列出的错误信息之一,并且退出。否则,评测程序示例首先依次打印出 construct_instructions(s, n, k, q)
所追加的指令。对于
随后,评测程序示例将依次处理测试用例。对于每个测试用例,评测程序示例将在该测试用例中的输入数据上运行所创建的程序。
对于每个 register t:
如果所有指令都被执行完毕,评测程序示例将打印出程序的输出结果。
如果
。
如果
。
在处理完所有测试用例后,评测程序打印出 number of instructions:
样例一
input
0 2 2 1000 0 0 1 3 3 1 2 2 -1
output
move 1 0 right 1 1 1 and 0 0 1 0 0 0 1
explanation
设
提供给程序的输入,总共有 4 种可能情形:
- 情形
: , - 情形
: , - 情形
: , - 情形
: ,
我们可以注意到,对于所有 4 种情形,
append_move(1, 0)
,追加一条指令,将 拷贝到 。append_right(1, 1, 1)
,追加一条指令,将 中的所有比特右移 位,接着将结果存回到 中。由于每个整数都是 -比特长的,这将使得 等于 。append_and(0, 0, 1)
,追加一条指令,将 和 做按位与,接着将结果存到 中。在本指令执行完毕后, 被设置成 和 的按位与,其值等于 和 的按位与,也就是所要求的结果。
样例二
input
1 2 1 1000 0 0 0 1 1 0 1 1 -1
output
move 1 0 right 1 1 1 and 2 0 1 or 3 0 1 left 3 3 1 or 0 2 3 0 0 0 1 0 1 1 1
explanation
设
append_move(1, 0)
append_right(1, 1, 1)
append_and(2, 0, 1)
append_or(3, 0, 1)
append_left(3, 3, 1)
append_or(0, 2, 3)
在执行完这些指令后,
数据范围与提示
对于所有数据:
(对于所有 )
子任务 | 分值 | 特殊限制 |
---|---|---|
hack 与评测
最终评测程序与样例评测程序输入格式相同,但是自定义数据组数不得超过
注意 hack 数据的范围必须严格遵守数据范围,即至少完全符合某一个子任务的限制。
评测程序只会输出操作序列,spj 将会使用输入文件内的自定义测试数据以及内部生成的若干组数据进行测试,若全部正确则该测试点判为正确,否则获得
时间限制:
空间限制: