解题过程
梦回高中数列问题,以下是推导过程($year[n]$表示经过$n$年后的机器人总数,设最初有$a$个机器人):
$year[0] = a$
$year[1] = year[0] + (2*year[0]-1)$
$year[2] = year[1] + (2*(year[1]-year[0])-1)$
$…$
$year[n] = year[n-1] + (2*(year[n-1]-year[n-2])-1)$
累加:$year[0] + … + year[n] = a + 3*(year[0]+…+year[n-1]) - 2*(year[0]+…+year[n-2]) - n$
整理:$year[n] = a + 2*year[n-1] - n$
变形:$year[n]-n + a-2 = 2*(year[n-1]-(n-1) + a-2)$
令$f(n) = year[n]-n + a-2$,则:
$f(n) = 2*f(n-1) = 2^{n-1}*f(1)$
将$f(n)$,$f(1)$代入,得:
$year[n]-n + a-2 = 2^{n-1}*(year[1]-1 + a-2)$
将$year[1] = year[0] + (2*year[0]-1) = 3a-1$代入并整理,得:
$a=\frac{year[n]-n-1}{2^{n+1}-1}+1$
python代码
n, s = map(int, input().split()) #n和s分别对应上式的n和year[n],代入公式即可
print((s-n-1) // (2**(n+1)-1) + 1)