from math import pow
def kAcornProblem(branches, k):
n = len(branches)
n_root_k = int(round(pow(n, 1/k)))
current = -1
lower_bound = 0
upper_bound = n-1
for curr_interval in range(k-1):
# for level in range(n_root_k):
# current += n_root_k
# if branches[current] == True:
# lower_bound = current - n_root_k + 1
# upper_bound = current
# break
if upper_bound - lower_bound <= n_root_k:
break
for curr in range(lower_bound, upper_bound+1):
if branches[curr] == True:
current = curr
break
return current
x = [False]*131000 + [True]*72
print(kAcornProblem(x, 17), 131000)
x = [False]*2047 + [True]*1
print(kAcornProblem(x, 11), 2047)
x = [False, False, False, False, True, True, True, True, True]
print(kAcornProblem(x, 2), 4)
x = [False]*16 + [True]*9
print(kAcornProblem(x, 2), 16)
x = [False]*37 + [True]*63
print(kAcornProblem(x, 2), 37)
x = [False]*0 + [True]*100
print(kAcornProblem(x, 2), 0)
x = [False]*99 + [True]*1
print(kAcornProblem(x, 2), 99)
x = [False]*25 + [True]*100
print(kAcornProblem(x, 3), 25)
x = [False]*32 + [True]*32
print(kAcornProblem(x, 3), 32)
x = [False]*21 + [True]*43
print(kAcornProblem(x, 3), 21)
x = [False]*3 + [True]*13
print(kAcornProblem(x, 4), 3)
x = [False]*0 + [True]*16
print(kAcornProblem(x, 4), 0)
x = [False]*10 + [True]*22
print(kAcornProblem(x, 5), 10)
