0349 兰顿蚂蚁
* * * *
拉格朗日计划
* * * *
兰顿蚂蚁

一只蚂蚁在涂有黑色或白色的网格上按如下规则移动:

若它在黑色方格上,那么它将当前方格变为白色,逆时针旋转90度,并向前移动一格。

若它在白色方格上,那么它将当前方格变为黑色,顺时针旋转90度,并向前移动一格。

从全白的网格开始,移动$10^{18}$次之后,有多少个方格是黑色的?

本题难度:



解答

可以验证,黑格数量的消长在充分多(大约1万多步)的步数后呈现周期性的变化,周期是104。

因此先模拟充分多的步数,再利用周期性即可得最终结果$115384615384614952$。

target=10**18
bound=12000
T=104

d={}
dx,dy=[-1,0,1,0], [0,-1,0,1]
x=y=k=0
a=[]

for i in range(bound):
    if d.get((x,y),0)==0:
        d[(x,y)]=1
        k=(k-1)%4
        a.append(1)
    else:
        d[(x,y)]=0
        k=(k+1)%4
        a.append(-1)  
    x+=dx[k]
    y+=dy[k]

print sum(a)+sum(a[-T:])*((target-bound)/T)+sum(a[-T:-T+(target-bound)%T])