# luis ulloa 3d
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):
jump = int(round(pow(n, (k-curr_interval-1)/k)))
for level in range(n_root_k): # partition
current += jump
if branches[current] == True:
lower_bound = current - jump
if lower_bound == -1:
lower_bound = 0 # small index error/edge case
upper_bound = current
break
if upper_bound - lower_bound <= n_root_k:
break
current = lower_bound # current is at the high bound now, should be lower_bound
assert(upper_bound-lower_bound <= n_root_k)
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)
