def naive(n,a,b): ans=2**63 def f(s): ans=0 for i in range(1,n+1): ans-=b*s[i] if i>i)&1: s[i+1]=1 else: s[i+1]=-1 ans=min(ans,f(s)) return ans def sol1(n,a,b): dp=[[2**63,2**63] for i in range(n+1)] dp[1][1]=-b dp[1][0]=b for i in range(2,n+1): dp[i][1]=min(dp[i-1][1]+a-b,dp[i-1][0]-a-b) dp[i][0]=min(dp[i-1][1]-a+b,dp[i-1][0]+a+b) return min(dp[n][1],dp[n][0]) def mul(a,b): n=len(a) res=[[2**63]*n for i in range(n)] for i in range(n): for j in range(n): for k in range(n): res[i][j]=min(res[i][j],a[i][k]+b[k][j]) return res def mpow(a,k): if k==1:return a res=mpow(a,k//2) res=mul(res,res) if k%2==1: res=mul(res,a) return res def sol2(n,a,b): M=[[a+b,-a+b],[-a-b,a-b]] M=mpow(M,n-1) dp0=min(M[0][0]+b,M[0][1]-b) dp1=min(M[1][0]+b,M[1][1]-b) return min(dp0,dp1) from random import randrange as rd cnt=0 while 0: cnt+=1 print(cnt) n,a,b=rd(2,100),rd(1,100),rd(1,100) #ansn=naive(n,a,b) ans1=sol1(n,a,b) ans2=sol2(n,a,b) if ans2!=ans1: print(n,a,b) break