例题6-6 小球下落 (Dropping Balls, UVa 679)

发布于 2020-09-21  108 次阅读

刘汝佳 《算法竞赛入门经典》 例题6-6 小球下落 (Dropping Balls, UVa 679) python实现
AcWing 1258 与本题基本一致，题目描述不太一样，内容是一样的，代码在AcWing中AC了。


有一棵二叉树，最大深度为D，且所有叶子的深度都相同。所有结点从上到下从左到右 编号为1, 2, 3,…, 2D-1。在结点1处放一个小球，它会往下落。每个内结点上都有一个开关， 初始全部关闭，当每次有小球落到一个开关上时，状态都会改变。当小球到达一个内结点 时，如果该结点上的开关关闭，则往左走，否则往右走，直到走到叶子结点。

一些小球从结点1处依次开始下落，最后一个小球将会落到哪里呢？输入叶子深度D和 小球个数I，输出第I个小球最后所在的叶子编号。假设I不超过整棵树的叶子个数。D≤20。 输入最多包含1000组数据。

AcWing上的要求是

输入格式：

一行包含两个用空格隔开的整数 D 和 I。

输出格式：

对应输出第 I 个小球下落停止时的叶子序号。

数据范围

2 ≤ D ≤ 20,
1 ≤ I ≤ 524288

输入样例：
4 2
Plain text
输出样例：
12
Plain text
def fa(x,y,switch):
    if(switch == 0):
        x = x+1
        y = y*2
        switch = 1
    else:
        x = x+1
        y = y*2+1
        switch = 0
    return x,y,switch

import sys
try:
    while True:
        line=sys.stdin.readline().strip()
        if line == '':
            break
        k,n=map(int,line.split())
except:
    pass

lst=[]
for j in range(1,k+1):
    temp = []
    for i in range(2**(j-1),2**j-1+1): #-1是最后一个，但range不包括，所以需要+1
        temp.append(0)
    lst.append(temp)

x = 0
y = 0
y_last = 0
for p in range(n):
    x , y = 0 , 0
    for j in range(k):
        switch = lst[x][y]
        x_temp,y_temp,switch = fa(x,y,switch)
        lst[x][y] = switch
        y_last = y # 取最后一个数的时候需要y值。
        x,y = x_temp,y_temp
print([i for i in range(2**(k-1),2**k-1+1)][y_last]) #因为直接存的0，1，没有再改。
Plain text
  1. 输入格式：
  2. 输出格式：
  3. 数据范围
  4. 输入样例：
  5. 输出样例：