!python -V
Python 3.5.5 :: Anaconda custom (64-bit)
首先让我们明确这道题的限制和目标,题目中给出了 20 个计算器上常见的一元函数,你需要通过这些一元函数实现逼近任意给定的浮点数。
一元函数有:sin, cos, tan, asin, acos, atan, sinh, cosh, tanh, asinh, acosh, atanh, exp, log, x^2, sqrt, -x, 1/x, R2D, D2R,我们把这个集合记为 $F$
形式化来说,对于任意 $y_0 \in \mathbb{R}$,构造 $\{f_k\}$ $(f_k \in F, k=1,...,n)$ 序列,记 $y = (f_n \circ f_{n-1} \circ ... \circ f_1)(0) = f_n(f_{n-1}(...f_1(0)))$,满足 $|y-y_0| < \epsilon$
本题中为了降低难度,取 $\epsilon = 10^{-5}$ 且 $y_0 \in (0, 100)$
一开始没有想到搜索能完成这道题目,但是在进行流量分析是发现有的 payload 明显没有模式,要么解题者是自己在草稿纸上算出来的,要么是搜索的结果,搜索算法很简单,就是枚举 $f$ 序列即可,但可能要进行适量的剪枝或者固定某些步骤的优化,在本地判断后没有问题,就可以提交了。注意:如果遇到搜不出来的情况,可以提交一个错误答案后尝试新的。
这个解法适用的情况很窄,如果取 $\epsilon = 10^{-9}$ 甚至我们只要求 $\epsilon > 0$,暴力搜索就不太可能做到。
观察题目中的这些函数,我们能很快构造出让屏幕上数字乘 2,除以 2 的序列(这里函数顺序为按键顺序):
乘 2:$x * 2 = exp, x^2, log$
除以 2:$x / 2 = exp, sqrt, log$
有了这两个新的「一元函数」,我们很容易联想到任何数字都有二进制表示,只要我们能加 1,就能通过一个数的二进制表示来构造任何数字,那么问题是怎么加 1 呢?
我们注意到有双曲函数恒等式:
$\cosh 2x\ = \cosh^2 x + \sinh^2 x = 2\cosh^2 x - 1 = 2\sinh^2 x + 1$
俗话说:一寸长,一寸强,这么长的公式肯定强。
我们将想要的目标形式 $x + 1$ 和这个公式放在一起观察。不难发现:
令 $t = 2\sinh^2 x$,即 $x = \rm{asinh}(\rm{sqrt}(t/2))$,那么:
$t + 1 = \cosh 2x = \cosh(2(\rm{asinh}(\rm{sqrt}(t/2))))$,换回去:
$x + 1 = \cosh(2(\rm{asinh}(\rm{sqrt}(x/2))))$
注意到右边用到了我们发现的两个新一元函数乘 2 和除以 2,仍然是完全的一元函数复合形式,我好了。
有了这个理论基础我们就可以编写代码,利用题目提供的 poc.py
,我们可以编写如下解题脚本:
import json
import requests
host = "http://202.38.93.241:10024"
class Calc:
def __init__(self):
self.ops = []
def op(self, name, *kws):
if name in dir(self):
getattr(self, name)(*kws)
else:
self.ops.append(name)
def mul2(self):
# 乘以 2
self.op('exp')
self.op('x^2')
self.op('log')
def div2(self):
# 除以 2
self.op('exp')
self.op('sqrt')
self.op('log')
def add1(self):
# 利用双曲函数公式加 1
self.op('div2')
self.op('sqrt')
self.op('asinh')
self.op('mul2')
self.op('cosh')
def addn(self, n):
# 利用多次加 1 加 n
for _ in range(n):
self.op('add1')
def solve(x):
# 二进制小数点后的位数
n = 20
calc = Calc()
# 利用除以 2 (相当于二进制右移)构造小数部分
for i in range(n):
if int(x * 2 ** (n - i)) % 2:
calc.op('add1')
calc.op('div2')
calc.op('addn', int(x))
seq = ','.join(calc.ops)
return seq
with requests.session() as sess:
r = sess.get(host + '/challenges')
X = json.loads(r.text)["msg"]
print(X)
data = {
"a1": solve(X[0]),
"a2": solve(X[1]),
"a3": solve(X[2])
}
r = sess.post(host + "/submit", data=data)
resp = json.loads(r.text)
print(resp["msg"])
[35.82831063699986, 80.6361952659885, 88.59694036265915] flag{you_are_good_at_using_calculators_by_amiya}
import json
import requests
host = "http://202.38.93.241:10024"
import sympy
EPS = 1e-7
class Calc:
def __init__(self):
self.ops = []
def op(self, name, *kws):
if name in dir(self):
getattr(self, name)(*kws)
else:
self.ops.append(name)
def mul2(self):
# 乘以 2
self.op('exp')
self.op('x^2')
self.op('log')
def div2(self):
# 除以 2
self.op('exp')
self.op('sqrt')
self.op('log')
def add1(self):
# 利用双曲函数公式加 1
self.op('div2')
self.op('sqrt')
self.op('asinh')
self.op('mul2')
self.op('cosh')
def addn(self, n):
# 利用多次加 1 加 n
for _ in range(n):
self.op('add1')
def solve(x):
# 将小数化为分数
p = int(x / EPS)
q = int(p / x)
# 计算连分数数组
cfs = sympy.ntheory.continued_fraction.continued_fraction_periodic(p, q, 0)
# 利用 addn 和 1/x 计算连分数
calc = Calc()
for k in cfs[::-1]:
calc.op('addn', k)
calc.op('1/x')
calc.op('1/x')
seq = ','.join(calc.ops)
return seq
with requests.session() as sess:
r = sess.get(host + '/challenges')
X = json.loads(r.text)["msg"]
print(X)
data = {
"a1": solve(X[0]),
"a2": solve(X[1]),
"a3": solve(X[2])
}
r = sess.post(host + "/submit", data=data)
resp = json.loads(r.text)
print(resp["msg"])
[8.537001664460819, 13.772290777666662, 90.89072584304898] flag{you_are_good_at_using_calculators_by_amiya}
这道题为了降低难度让很多低精度方法也能通过,所以应该有很多近似方法可以解出本题,如果你有有趣的解法欢迎 PR 投稿。
在比赛过程中也有很多人询问为什么会 system error,我想把这个问题连同下面的思考题一起留作课后作业:
为什么会 system error?
为什么在构造 add1
时,选择了 $[1]\ \cosh 2x\ =[2]\ \cosh^2 x + \sinh^2 x =[3]\ 2\cosh^2 x - 1 = [4]\ 2\sinh^2 x + 1$ 中的 $[1] = [4]$ 而不是 $[1] = [3]$ ?
题目代码已经上传到本目录 src
下。