In [1]:
!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,我们可以编写如下解题脚本:

In [5]:
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}

解法三:连分数

有人可能要问:能不能再给力一点?

上面的二进制解法基本可以满足比较高的精度要求,但是有没有一个甚至没有理论误差的方法?

答案是显然的:如果我们有一个数的精确连分数表达,那么我们可以用题目限制下的函数构造没有理论误差的计算公式。

关于连分数请参看 维基百科:连分数,对于有理数,连分数分解算法可以用简单的辗转相除得到,我们这里将目标近似为一个有理数(这里引入了部分误差),然后对其进行连分数分解,最后利用 addn1/x 完成连分数的计算:

In [7]:
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 下。