自动搬运

查看原文

来自洛谷，原作者为

	EricWan 一只菜鸡。

搬运于2025-08-24 23:16:44，当前版本为作者最后更新于2025-06-09 21:36:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

六个寄存器，真空指令集。
限制卡得紧，一堆子问题。
先乘解决除，取负能造一。
分支不让用，咋判二的幂。
与上零负一，创造新奇迹。
数除动分母，官解太诡异。
溢出不用急，偶数先右移。
一错调一天，这题真猎奇。

先放一个经过微调的 checker，能更好的快速对代码进行测试，分屏放代码和 checker 也可以看完所有数据而不让输入输出混淆。简直是 debug 神器。

#include<iostream>
#include<string>
#include<fstream>
#include<sstream>
#include<vector>
#include<map>
#include<cmath>
#include<bitset>
using namespace std;
#define Reg unsigned long long
map<string,Reg> regs;
int line=0;
void die(string msg){
	cout<<"Line "<<line<<": "<<msg<<endl<<endl;
	//exit(1);
}
Reg& reg(string id){
	if(id=="a"||id=="b"||id=="c"||id=="d")id="r"+id+"x";
	if(id=="x")id="rsi";
	if(id=="y")id="rdi";
	if(regs.find(id)==regs.end())die("accessing invalid register: "+id);
	return regs[id];
}
Reg num(const string&str){
	Reg n=0;
	stringstream ss("");
	ss<<str;
	ss>>n;
	return n;
}
char cases[100];
ostream &XXXXX(cout << "Code file : ");
istream &XXX(cin >> cases);
std::ifstream code(cases);
//#define debug4
#ifdef debug4
Reg ch4x, ch4y, ch4d;
#endif
void initreg(int type){
	regs["rax"]=regs["rbx"]=regs["rcx"]=regs["rdx"]=regs["rsi"]=regs["rdi"]=0;
	int cnt;
	cout << "Input register number : ";
	cin >> cnt;
	if (cnt) {
		cout << "Input " << cnt << " register" << (cnt - 1 ? "s :\n" : " :\n");
	} else {
		cout << "no input";
	}
	if (cnt) {
		cout << "x = ";
		cin >> regs["rsi"];
		#ifdef debug4
		ch4x = regs["rsi"];
		#endif
	}
	if (cnt >= 2) {
		cout << "y = ";
		cin >> regs["rdi"];
		#ifdef debug4
		ch4y = regs["rdi"];
		#endif
	}
	if (cases[0] == '1') {
		cout << "need\n" << regs["rsi"] * 4080 << endl;
	} else if (cases[0] == '2') {
		cout << "need\n" << regs["rsi"] / 4080 << endl;
	} else if (cases[0] == '3') {
		cout << "need\n" << 4080 << endl;
	} else if (cases[0] == '4') {
		cout << "need\n" << regs["rsi"] * regs["rdi"] << endl;
	} else if (cases[0] == '5') {
		cout << "need\n" << regs["rsi"] / regs["rdi"] << endl;
	} else if (cases[0] == '6') {
		cout << "need\n" << (unsigned long long)sqrtl(regs["rsi"]) << endl;
	} else if (cases[0] == '7') {
		Reg ans = 1;
		while (ans < regs["rsi"]) ans <<= 1;
		cout << "need\n" << ans << endl;
	}
}
int main(){
	string cmd;
	initreg(0);
	while(getline(code,cmd)){
		vector<string> toks;
		stringstream ss("");
		string tok;
//		cout << "code = " << cmd << endl;
		if (cmd.substr(0, 5) == "print") {
			cout << cmd.substr(6) << endl;
			continue;
		}
		if (cmd == "debug_all") {
			cout << "debug_all" << endl;
			for (string i : {"a", "b", "c", "d", "x", "y"}) {
				cout << i << " = " << reg(i) << endl;
			}
			continue;
		}
		if (cmd.substr(0, 12) == "debug_all(b)") {
			#ifdef debug4
			if (cmd[13] == '*') {
				if (ch4x & 1)
				{
					ch4d += ch4y;
				}
				ch4x >>= 1;
				ch4y <<= 1;
			}
			#endif
			cout << "debug_all(b)" << endl;
			for (string i : {"a", "b", "c", "d", "x", "y"}) {
				cout << i << " = " << bitset<64>(reg(i)) << endl;
				#ifdef debug4
				if (i == "d") {
					cout << "D = " << bitset<64>(ch4d) << endl;
				}
				#endif
			}
			continue;
		}
		if (cmd == "debug") {
			cout << "debug" << endl;
			for (string i : {
			#if 0
			"a", "b", "c",
			#endif
			"d", "x", "y"
			}) {
				cout << i << " = " << reg(i) << endl;
			}
			continue;
		}
		line++;
		for(auto a:cmd)if(a==';')break;else ss<<(a==','?' ':a);
		while(ss>>tok)toks.push_back(tok);
		if(toks.size()<=0)continue;
		if(toks.size()==3-(toks[0]=="!"||toks[0]=="?"||toks[0]=="read"||toks[0]=="write")){
			string o=toks[0];
			if(o=="+"||o=="add")reg(toks[1])+=reg(toks[2]);
			else if(o=="-"||o=="sub")reg(toks[1])-=reg(toks[2]);
			else if(o=="^"||o=="xor")reg(toks[1])^=reg(toks[2]);
			else if(o=="<"||o=="shl")reg(toks[1])<<=num(toks[2]);
			else if(o==">"||o=="shr")reg(toks[1])>>=num(toks[2]);
			else if(o=="!"||o=="write") {
//				cout << reg(toks[1]) << endl;
				printf("%30llu\t", reg(toks[1]));
				cout << toks[1] << " = " << bitset<64>(reg(toks[1])) << endl;
			}
			else if(o=="?"||o=="read")cin>>reg(toks[1]);
			else if(o=="="||o=="movabs")reg(toks[1])=num(toks[2]);
			else if(o=="*"||o=="mul")reg(toks[1])*=reg(toks[2]);
			else if(o=="/"||o=="div")reg(toks[1])/=reg(toks[2]);
			else die("unknown instruction");
		}
		else die("unknown instruction or missing arguments");
	}
	system("pause");
	return 0;
}

后文若没有明确说明，所有除法都是向下取整。

A

$$4080x=4096x-16x=2^{12}x-2^4x$$

加法进行赋值，位移处理，减法解决。

+ y x
< y 4
< x 12
- x y
! x

B

$$\frac x{4080}=\frac{2^kx}{2^k\times4080}=\frac{x\times\frac{2^k}{4080}}{2^k} $$

我们只需要试一遍所有不超过 $64$ 的 $k$，手动计算 $\frac{2^k}{4080}$，拆位，用位移和加法实现乘法，一边处理一边向另一个寄存器输出，最后让那个寄存次进行位移即可。

经过尝试，偷看题解，我们找到了合适的 $k=43$。其实这个 $k$ 是可以计算得到的，为什么，是因为我们需要让 $k$ 尽量大（精度更高），然而让 $\frac{2^k}{4080}$ 乘给的 $x$ 不超过 $64$ 位。于是，我们用计算器摁出最大的 $k$ 使得 $\frac{2^k}{4080}<2^{32}$ 即可。最后贴一下分解，省着太懒的读者按计算器花时间。

$$\frac{2^k}{4080}=2155905153=\sum\limits_{i\in\{0,7,15,23,31\}}2^i $$

+ y x
< x 7
+ y x
< x 8
+ y x
< x 8
+ y x
< x 8
+ y x
> y 43
! y

这只有 11 条指令，出题人，快点把 16 改小。

C

常数节点，哦对不能用。但是我们可以用官方题解。

想要常数，我们可以先想办法把这个值域很大的 $x$ 值域缩小。

一个很妙的做法就是把这个数取负。

如果 $x\ge2^{63}$ 那么 $x$ 的最高位一定是 $1$，若 $x\le2^{63}$ 那么 $-x$ 的最高位一定是 $1$，则 (x>>63)+((-x)>>63) 仅可能为 $1$ 或 $2$，我们把这个 $1$ 或 $2$ 再次取负我们就可以得到一个前缀有非常多的 $1$ 的数。

因为 $(4080)_{10}=(111111110000)_2$ 位移两次再相减。

- y x
> x 63
> y 63
+ x y
- a x
> a 52
+ b a
> a 8
- b a
! b

这只有 10 条指令，出题人，快点把 16 改小。

D

定义 $\&$ 为二进制按位与。

根据 A 的思路我们想到可以拆位，拆位可以不断把给定的一个数右移（不妨为 $x$），把另一个数左移（不妨为 $y$）。实际上，这样做指令条数比较多（似乎是多一条无用的移 $x$ 指令），我们也可以从低到高扫描 $x$ 的每一位，并对 $y$ 不断左移，每次对 $x$ 进行位提取即可。

于是我们的思路如下：

for i in range(64) :
	if x & (1 << i) != 0 :
		cnt += y
	y <<= 1

循环我们展开，位移，累加都好解决，但是这是旷野小计算，指令集很小，没有分支。

我们偷看题解后发现，其实 cnt += y 等价与 cnt += y * (1 if x & (1 << i) != 0 else 0)。

获取 $x$ 的特定位，我们可以先左移后右移。设这一位是 $a\in\{0,1\}$。

然后 $cnt$ 就为每一步下的 $y\times a$ 之和。

于是我们的量乘问题，一点都没有解决。（是吗？）

我们发现我们的问题变成了求一个数乘 $1$ 或 $0$ 的结果，后面是很关键的一步，继续偷看题解发现 $b\in\{0,1\}$ 时 $a\times b=a\&-b$，这是非常好证明的。

最后解决 $\&$，我们都知道 $2\times(a\&b)=a+b-(a\oplus b)$，问题解决了。

细节：按位与的加法可能超过数据范围，被忽略掉一个最高位，我们发现我们只需要把需要乘的那个 $0$ 或 $-1$ 拆出最高位和剩下的位，分别做两次与即可。高级语言循环体的第二次执行及以后，$y$ 都是 $2$ 的倍数，直接右移后做 $\&$ 做即可。

另一个细节：大常数选手指令条数太多了那不全分。我们可以认真思考自己的代码上一步会让寄存器的变量的值赋为什么，针对上一次的赋值范围适当减少初始化指令次数。

776 行，不知道为什么要放那么迷惑的 1024 行作为限制，我曾经以为我的 1200+ 的解很接近正解了，实际上差得远。

用可读性极差的代码，生成不可读的代码，最后眯着眼睛看根本没有可读性的测试输出。T_T

for (int i = 0; i < 64; i++) {
	if (i == 63) {
		cout << "^ b b" << endl;
	}
	cout << "+ b x" << endl;
	if (i < 63) {
		cout << "< b " << 63 - i << endl;
	}
	cout << "> b 63" << endl; // b = bool(x & (1 << i))
	if (i == 0) {
		cout << "- x b" << endl;
	}
	if (i) {
		cout << "^ a a" << endl;
		cout << "^ c c" << endl;
	}
	if (i == 0) {
		cout << R"(- a b
> a 1
+ c a
+ c y
^ a y
- c a
> c 1
+ d c
> a 63
+ b a
> b 1
< b 63
+ d b
< y 1
> y 1
)";
	} else {
		cout << R"(- a b
+ c a
+ c y
^ a y
- c a
+ d c
< y 1
)";
	}
}
cout << "! d";

这只有 776 条指令，出题人，快点把 1024 改小。

E

官解里写的高级语言代码怪怪的，为什么是 > 不是 >=，为什么是 y -= b 不是 x -= y << i？正确性应当被怀疑？

先自己给出一份高级语言的龟速除代码

x, y = map(int, input().split())
d = 0
print(x // y) # 保证正确答案
for i in range(63, -1, -1) :
	b = x >> i
	if b >= y :
		d += 1 << i
		x -= y << i
print(d) # 计算出的答案

循环自然是手动展开，b >= y 等价与 b - y 的最高位是 0，换句话说，我们只有在 $\frac{\frac x{2^i}-y}{2^{63}}\oplus1=1$ 时执行下面的两条累加。

官解里说什么【有 1 << i 这个表达式，所以需要用 case 3 的办法造出常数 $1$ 来。】有点糖，(1<<i)*(b-y>>63) 不是可以写成 b-y>>63<<i 吗？

好吧还是似乎需要造个 $1$，方便 $\frac{\frac x{2^i}-y}{2^{63}}\oplus1$，题目保证 $y\neq0$，用 $y$ 造一个即可。

这里又遇到了 (y << i) & ... 其中 ... 为 $-1$ 或 $0$ 的情况，我们同样使用乘法的 trick 即可（也就是按位与的两侧如果先除以二无影响，则先除以二避免加法溢出）。可是我们发现，$i=0$ 的时候这个右移后与再左移的 trick 并不使用，但是我们的 $i$ 是从大到小枚举的，换句话说，$i=0$ 的时候我们根本不需要处理我们的那个 x -= y << i！

// 无脑维护，使劲调试，高达十二分！
cout << R"(+ b y
- c y
> b 63
> c 63
- a b
- a c
> a 63
)"; // 造 1 的代码，a = 1
for (int i = 63; i >= 0; i--) {
	cout << "^ b b" << endl;
	cout << "^ c c" << endl;
	cout << "+ b x" << endl;
	if (i != 0) cout << "> b " << i << endl;
	cout << "- b y" << endl;
	cout << "> b 63" << endl; // b = 0 if x >> i >= y else 1
	cout << "^ b a" << endl; // b = 1 if x >> i >= y else 0
	// 然后 d += b << i
	if (i != 0) cout << "< b " << i << endl;
	cout << "+ d b" << endl;
	if (i != 0) cout << "> b " << i << endl;
	if (i != 0) { // 然后 x -= (y << i) & c
		cout << "- c b" << endl; // c = 0xffff if x >> i >= y else 0
		cout << "> c 1" << endl; // c = 0x7fff if x >> i >= y else 0
		cout << "- x c" << endl;
		if (i == 1) {
			cout << "- x y" << endl;
			cout << "^ c y" << endl;
		} else {
			cout << "^ b b" << endl;
			cout << "+ b y" << endl;
			cout << "< b " << i - 1 << endl;
			cout << "- x b" << endl;
			cout << "^ c b" << endl;
		}
		cout << "+ x c" << endl;
	}
}
cout << "! d";

突然发现，题目保证 $x,y\le2^{32}$，删除几条防溢出的指令。这样我们就只需要在内层循环再卡两条指令就可以了。等等，题目保证 $x,y\le2^{32}$？那么我们把枚举的 $i$ 从 $31$ 开始就可以了。

cout << R"(+ b y
- c y
> b 63
> c 63
- a b
- a c
> a 63
)"; // 造 1 的代码，a = 1
for (int i = 31; i >= 0; i--) {
	cout << "^ b b" << endl;
	cout << "^ c c" << endl;
	cout << "+ b x" << endl;
	if (i != 0) cout << "> b " << i << endl;
	cout << "- b y" << endl;
	cout << "> b 63" << endl; // b = 0 if x >> i >= y else 1
	cout << "^ b a" << endl; // b = 1 if x >> i >= y else 0
	// 然后 d += b << i
	if (i != 0) cout << "< b " << i << endl;
	cout << "+ d b" << endl;
	if (i != 0) cout << "> b " << i << endl;
	if (i != 0) { // 然后 x -= (y << i) & c
		cout << "- c b" << endl; // c = 0xffff if x >> i >= y else 0
		// cout << "> c 1" << endl; // c = 0x7fff if x >> i >= y else 0
		cout << "- x c" << endl;
		if (i == 1) {
			cout << "- x y" << endl;
			cout << "^ c y" << endl;
		} else {
			cout << "^ b b" << endl;
			cout << "+ b y" << endl;
			cout << "< b " << i - 1 << endl;
			cout << "- x b" << endl;
			cout << "^ c b" << endl;
		}
		cout << "+ x c" << endl;
	}
}
cout << "! d";

如果被允许看官方题解，感觉难度和乘法差不多。

这只有 570 条指令（因为数据范围小），出题人，快点把 1024 改小。

F

开根，困难。

~作者太菜，不会，全力在研究，出不了几天估计就能补上。~

根据 E 题的传奇官解代码出错行为，F 又没有什么做法解释，抛开官解理论部分自己先研究一下。

手撕平方根？曾经数学老师交过，学案丢了。迅速补一下，推荐这个视频。

容易发现，还是降序枚举位，确定到底能不能再放一个 $1$。check 的复杂度如果是乘法，那么会爆得很离谱，根据我的 775 步 $64$ 位乘法解，需要大约 390 步完成 $32$ 位乘法，加一些小优化（就是只枚举已经填过数的哪些位，后缀 $0$ 不用管），预估需要 6500 步左右。

考虑优化，使用手撕平方根算法。何为手撕平方根算法？

计算乘法的复杂度太高了，假设枚举到第 $i\in[0,31]$ 位，如果我们记录之前算过的 $[i+1,31]$ 这些位的乘积 $S$，我们能优化很多复杂度。这就是手撕平方根算法的核心思路。我们记录已经放的位的乘积 $S$ 与前面这些位的值 $a$，我们只需要比较 $S+a\times2^{i+1}+2^{2i}$ 和 $x$ 即可，若小于等于 $x$，更新 $S$ 为这个结果，否则不动。这个分支结构看似复杂至极实际非常困哪，用我们刚才 E 的处理有关分支取决于数的大小的方法大概也能做出来。

写出高级语言代码进行检测：

x = int(input())
print(x ** 0.5)
a = 0 # a
b = 0 # S
for i in range(31, -1, -1) :
	if b + (a << (i + 1)) + (1 << (2 * i)) <= x :
		b += (a << (i + 1)) + (1 << (2 * i))
		a += 1 << i
print(a)

于是式子是正确的，进行优化：

x = int(input())
print(x ** 0.5)
a = 0 # a
b = 0 # S
c = 1 # 官解用的 c 存储 1，跟官解一样吧
for i in range(31, -1, -1) : # 后面的代码就是依照上面的式子模拟
	d = a;
	d <<= i + 1
	d += c << i * 2
	# print(d)
	# print((a << (i + 1)) + (1 << (2 * i)))
	a += ((b + d - 1 - x) % (1 << 64) >> 63) << i
	# 这个东西二进制下只有一个 1，可以直接用 (b+d-1-x>>63)<<i 得到
	if b + d <= x :
		b += d
print(a)

这题也会用到前面的“$i=0$ 不处理”“先位移后加减”等 trick，但是指令生成器代码更长，细节更多。

写代码的过程中，我们发现我们有可能用“相减再取最高位”的方法会出错，因为这题数据范围太大了。为了解决这个问题，我的方法是这样的：外层枚举 $i$ 的过程中，若 $i$ 比较大，才会出现这个情况，但是我们 $i$ 比较大的时候需要比较的数都与末几位无关（因为那个表示面积的 $S+d$ 是二的很大的整数幂的倍数），把 $S+d$ 和 $x$ 先右移 $2$ 再比较即可，对于 $i$ 比较小的情况，因为前几位已经对 $x$ 进行了一些逼近了，我们用刚才的朴素做法做也不会溢出。（没有判溢出是可以过自己测的小数据的，但是 SPJ 大概是用的按位逻辑推理评测的代码，难以通过。）

比乘法和除法难得多，但是很有趣。（除了做法名字，这题官解我没看，很高兴。）

// 懒得删调试了
cout << R"(+ a x
- b x
> a 63
> b 63
- c a
- c b
> c 63
^ a a
^ b b
)"; // 造 1 的代码，c = 1
for (int i = 31; i >= 0; i--) {
	/*
	if (i == 31) { // 作者想对 31 再卡卡，但是 WA 了，懒得调，反正 30 处理对了，31 和 30 一个逻辑一起处理了就多几条指令
		cout << "^ d d" << endl;
		cout << "+ d x" << endl;
		cout << "> d 62" << endl;
		cout << "^ a a" << endl;
		cout << "- a d" << endl;
		cout << "> a 63" << endl;
		cout << "+ b a" << endl;
		cout << "< b 31" << endl;
		cout << "< a 62" << endl;
		continue;
	}
	*/
	if (i < 31) cout << "^ d d" << endl;
	cout << "+ d a" << endl;
	if (i < 30)
		cout << "< d " << i + 1 << endl;
	else
		cout << "< d " << i - 1 << endl;
	if (i < 30) {
		if (i) cout << "< c " << i * 2 << endl;
	} else {
		cout << "< c " << i * 2 - 2 << endl;
	}
	cout << "+ d c" << endl;
	if (i < 30) {
		if (i) cout << "> c " << i * 2 << endl;
	} else {
		cout << "> c " << i * 2 - 2 << endl;
	}
	if (i < 31) cout << "^ y y" << endl;
	cout << "+ y b" << endl; // 可能会越界，把所有比较操作先右移
	if (i >= 30) cout << "> y 2" << endl;
	cout << "+ y d" << endl;
	cout << "- y c" << endl;
	if (i >= 30) {
		// 空间不够，覆盖已经据算掉的 d
		cout << "^ d d" << endl;
		cout << "+ d x" << endl;
		cout << "> d 2" << endl;
		cout << "- y d" << endl;
		// 然后才计算真实的 d
		cout << "^ d d" << endl;
		cout << "+ d a" << endl;
		cout << "< d " << i + 1 << endl;
		cout << "< c " << i * 2 << endl;
		cout << "+ d c" << endl;
		cout << "> c " << i * 2 << endl;
	} else {
		cout << "- y x" << endl;
	}
	// cout << "! y" << endl;
	cout << "> y 63" << endl;
	// 上面计算好了 d 和分支参数 y
	// cout << "print add square size=" << endl;
	// cout << "! d" << endl;
	// cout << "print if y == 1, can add" << endl;
	// cout << "! y" << endl;
	if (i) cout << "< y " << i << endl;
	cout << "+ a y" << endl;
	if (i == 0) {
		break;
	}
	cout << "> y " << i << endl;
	// 后续如果 y = 1，那么 b += d，否则 b += 0
	// 但是寄存器被用完了
	// y 的计算需要 d，但是 d 只需要计算原先的 a，原先的 a 需要 y
	// 发现先让 -y 覆盖当前的 d，然后把 -y 倒腾会 y 寄存器
	cout << "^ d d" << endl;
	cout << "- d y" << endl;
	cout << "^ y y" << endl;
	cout << "+ y d" << endl;
	// 用 d 寄存器计算 2 ^ i * -y ，再加一下当前的 a 可以还原上一步结束的 a
	if (i) cout << "< d " << i << endl;
	// cout << "! d" << endl;
	cout << "+ d a" << endl;
	cout << "< d " << i + 1 << endl;
	// cout << "print c should be 1" << endl;
	// cout << "! c" << endl;
	if (i) cout << "< c " << i * 2 << endl;
	cout << "+ d c" << endl;
	if (i) cout << "> c " << i * 2 << endl;
	// 上面重新计算 d
	// 让后 b += d & y
	// d 是矩形新增面积（看我贴链接的那个视频）
	// 因为 i>0 才处理，d 和 y 都提前右移是可以的
	cout << "> d 1" << endl;
	cout << "> y 1" << endl;
	// cout << "! d" << endl;
	// cout << "! y" << endl;
	cout << "+ b d" << endl;
	cout << "+ b y" << endl;
	cout << "^ y d" << endl;
	cout << "- b y" << endl;
	// cout << "! a" << endl;
	// cout << "! b" << endl;
}
cout << "! a";

1000 行，卡得紧，好险。

update 20250617：做复杂了，这题其实不需要“记录 $S$”再比较 $S+d$ 和 $x$，又为了避免空间不够，覆盖 $d$ 再计算 $d$，其实可以直接维护在 $x$ 寄存器中维护 $x-S$，代码会少很多。怎么说呢，我只用五个可写寄存器和一个只读寄存器在限制内完成了标算（可能）需要六个可写寄存器完成的问题（不知道该不该高兴）。至于那个简单做法，我也不想写了，跟上面的差不了太多。

G

为什么官解里管这个问题叫做容量，不清楚，但是可以很快写出高级语言代码。

x = int(input())
x = x - 1
x |= (x >> 1)
x |= (x >> 2)
x |= (x >> 4)
x |= (x >> 8)
x |= (x >> 16)
x |= (x >> 32)
x = x + 1
print(x);

意思是：让 $x-1$ 的 topbit 覆盖全部后方的二进制位，然后加一。

首先我们肯定需要根据 $x\neq0$ 造一个 $1$ 先存着，将 $x-1$，最后将 $x+1$。

后文规定 $|$ 为二进制按位或。

中间计算过程中，位移是好实现的，按位或可以拆 $a|b=a+b-\frac{a+b-(a\oplus b)}2$。想办法卡卡就可以过，感觉没有 D 难。

cout << R"(+ b x
- c x
> b 63
> c 63
- a b
- a c
> a 63
- x a
)";
for (int i : {1, 2, 4, 8, 16, 32}) {
	cout << "^ b b" << endl;
	cout << "^ c c" << endl;
	if (i != 1) {
		cout << "^ d d" << endl;
	}
	cout << "+ b x" << endl;
	cout << "> b " << i << endl;
	cout << "+ c b" << endl;
	cout << "+ c x" << endl;
	cout << "+ d b" << endl;
	cout << "^ d x" << endl;
	cout << "- c d" << endl;
	cout << "> c 1" << endl; // c = x & b
	cout << "+ x b" << endl; // x' = x + b
	cout << "- x c" << endl; // x' = (x + b) - (x & b) = x | b
}
cout << "+ x a" << endl;
cout << "! x";

这只有 87 条指令，出题人，快点把 96 改小。

评价

是一个很有意思的题目，难度不是很高（但我支持它是黑，我的意思是，没有旷野大计算难），但是有点 Educational。

BCDE 的限制卡得不严，让人做出一个自己满意的解后会高兴更久。

里面有几个很有趣的 trick 例如按位与先位移后计算避免先计算后位移的加法溢出。

好题，可是洛谷没有 upvote 功能。

完整答案

完整的答案有点小长，放在这里了。