用一些节点构造10台计算机, 分别实现不同的指定功能.
所有运算为浮点运算, 可以精确到小数点后90位. 与期望输出相差不超过10^-9判为正确.
节点的类型: I/O, 加法, 取相反数, 加上常数, 乘/除以2^k, 取S(x)=1/(1+e^-x), 比较 (返回-1/0/1), 取Max, 乘法. 使用最后3种会扣分. 要求节点总数尽量少.
详见: uoj #224
vfk的讲题课件很清晰, uoj群的里有修正后的版本.
以下不加区分地使用等于和约等于.
-2a-2b Problem
仔细阅读题面.
1/(1+e^(17a)) Problem
仔细阅读题面.
sgn
不扣分的节点中, 最奇怪的要数S型节点. 观察图象, 发现当x->oo, S(x)->1; x->-oo, S(x)->0. 于是, 可以认为P(x) = S(x<<150) = 0 if x<0, 0.5 if x=0, 1 if x>0. 变换后即得sgn(x).
|a|
快一年了还是不会做这个点 TAT
想着用两个Sigmoid叠加造一个偶函数出来, 但是没法还原成线性的......
|a| = max { a, -a } = a + max { 0, -2a } = a - 2 min { 0, a }令P'(x) = P(x+eps) = 0 if x<0, 1 if x≥0.
考虑S(x+P'(x)<<500), 当x为非负数, 它等于1, 当x为负数, 它等于S(x). S'(0)=1/4. 当x->0, S(x)->x/4+0.5, 可解出x. 而x为非负数时, 用P'(x)凑一凑, 可调整为0. 于是, 我们实现了 min { 0, a }.
P'(x)<<500中的500是可以调整的, 只要结果充分大. 此处置为152可减少一个节点, 获得满分.
二进制转十进制
直接转换即可.
十进制转二进制
从低位向高位转换需要整除, 取模这些东西, 实现起来不方便.
所以, 考虑从高位向低位转换.
我的思路是这样:
a = in()
for i = 31 downto 0
b[i] = x >= (1<<i)
x -= b[i] ? 1<<i : 0
out(b)然后就不会捉了......没法只用190个节点.
正解是这样:
a = in()
for i = 31 downto 0
b[i] = x >= (1<<i)
x -= b[i] << i
out(b)卡一卡常数. 比如, 把所有数左移100位, 最低一位直接输出:
n = 32
print('I')
print('< 1 100')
y = 2
now = 3
for i in range(n-1, 0, -1):
t = -2**(i+100) + 2**10
print('C {} {}'.format(y, t))
print('S {}'.format(now))
print('- {}'.format(now+1))
print('< {} {}'.format(now+2, i+100))
print('+ {} {}'.format(y, now+3))
print('O {}'.format(now+1))
y = now+4
now += 6
print('> {} 100'.format(y))
print('O {}'.format(now))xor
先把a,b转成二进制, 按位异或, 再转回十进制.
x xor y = (x+y) mod 2 = x+y-(x+y >= 2 ? 2 : 0) (x,y in {0, 1})然而我在考虑这个......TAT
x xor y = min { x+y, 2-(x+y) }除以一般常数
把1/10转成二进制小数再倍增一下?
然而满分需要节点数不超过7.
正解很有趣:
(s(x0+dx)-s(x0))/dx = s'(x0)
=> dx s'(x0) = s(x0+dx) - s(x0)解出满足s'(x0)=0.1的x0即可. 注意上式仅在dx充分小时成立, 因此需要将x先缩小, 乘完之后再放大.
我写了一个牛顿切线法解方程的小程序. 实测double精度不够, 所以用了Python里的decimal.
from decimal import *
getcontext().prec = 90
e = Decimal('2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382179')
def g(x):
t = e ** -x
return t * (1 + t) ** -2
def h(x):
t = e ** -x
return (e ** (-2 * x) - t) * (1 + t) ** -3
def solve(c):
x = Decimal('2')
for i in range(1000):
x -= (g(x) - c) / h(x)
return x
print(solve(Decimal('0.1')))考场上难以得知e精确到小数点后90位的结果, 所以......用极限逼近一下?
也可以直接解出s'(x0)=0, 但是表达式包含ln, math模块里的精度不够.
排序
没有if语句, 遗忘选择排序 (排序网络) 会比较方便. bubble-sort即可.
乘法取模
基本思想是用 "快速加" 代替乘法, 这样只用对 [0, 2m) 内的数取模. a mod m = 1*a mod m.
a*b的快速加可以用泰勒展开代替: s(x + ln 3) = 1/4 + 3/16 x + 3/64 x^2 - 1/256 x^3 - 5/1024 x^4 + O(x^5), 由此构造 x^2, 而 ab = ((a+b)^2 - (a-b)^2)/4.
虽然意思领会了......但还是不会用不超过2000个节点实现.
抽象出一个F函数, 算是实现一下条件表达式.
生成第一种解法的Python代码如下:
def I():
print('I')
def O(x):
print('O %d' % (x))
def A(x, y):
print('+ %d %d' % (x,y))
def C(x, c):
print('C %d %s' % (x,c))
def N(x):
print('- %d' % (x))
def L(x, k):
print('< %d %d' % (x, k))
def R(x, k):
print('> %d %d' % (x, k))
def S(x):
print('S %d' % x)
T = 1
n = 32
def F(c, x):
'''x <= 0 ? c : 0
p = S((x-1e-15)<<150)<<151
s = S((c>>150) + p)
r = ((s-0.5)<<152) - p'''
global T
C(x, '-0.000000000000001') # 0
L(T, 150) # 1
S(T+1) # 2
L(T+2, 151) # 3 (p)
N(T+3) # 4 (-p)
R(c, 150) # 5
A(T+5, T+3) # 6
S(T+6) # 7 (s)
C(T+7, '-0.5') # 8
L(T+8, 152) # 9
A(T+9, T+4) # 10 (r)
T += 11
return T-1
def convert(y):
global T
b = []
L(y, 100)
y = T
T += 1
for i in range(n-1, 0, -1):
t = -2**(i+100) + 2**10
C(y, '%d' % (t))
S(T)
N(T+1)
L(T+2, i+100)
A(y, T+3)
b.append(T + 1)
y = T + 4
T += 5
R(y, 100)
b.append(T)
T += 1
return b
def MulMod(a, b, m):
global T
R(1, 10000)
r = T
T += 1
for i in range(n-1, -1, -1):
N(r) # 0
N(a) # 1
A(T, T+1) # 2
A(T+2, m) # 3
T += 4
f = F(m, T-1)
N(f) # 0
A(a, T) # 1
N(b[i]) # 2
C(T+2, '1') # 3
T += 4
f = F(T-3, T-1)
A(r, f) # 0
r = T
L(a, 1) # 1
N(T+1) # 2
A(m, T+2) # 3
T += 4
f = F(m, T-1)
N(f) # 0
A(r+1, T) # 1
a = T+1
T += 2
return r
def main():
global T
I() # a
I() # b
I() # m
T += 3
m = 3
R(1, 10000)
C(T, '1')
T += 2
a = MulMod(T-1, convert(1), m)
O(MulMod(a, convert(2), m))
main()3330个节点, 7分.
未完待续
97/100
yyt爷在考场上短短的几个小时就拿到了这个分......Orz
提交答案题还是挺有趣的. 人类来提供思路, 再用计算机辅助我们解决问题. APIO T2 我忘了自己还有台电脑, 手玩挂得很惨......QAQ