[PYTHON] How to solve the recursive function that solved abc115-D

problem

https://atcoder.jp/contests/abc115/tasks/abc115_d

The second challenge. I was really happy to solve it. This kind of problem is surprisingly important because it is also asked on other competition professional sites.

Direction

It is not hard to imagine that a recursive function would be used from the problem statement. The problem is that if you make a simulator, all the burger elements will be huge, so it is impossible. Think about what you need and use arithmetic to solve it efficiently.

What is difficult

There is no problem in interpreting the problem. The question is whether the conditions for recursion and the return value can be determined correctly. In addition, the fact that there are many conditional branches also raises the difficulty level.

solution

I felt that the trick of the recursion problem was to model the state phase with a small number of values. In other words, the following two things are important

1. Since the function is called recursively, create a function that holds for all of N, N-1, N-2 ... 1, 2.

2. Consider the termination conditions.

3. Since the function is called recursively, create a function that holds for all of N, N-1, N-2 ... 1, 2.

Since what is needed in this problem is the current location of the dachshund and the dimension of the burger, we take those two as arguments.

2. Consider the termination conditions.

This time there is an easy-to-understand end condition called level 0 burger, so use this.

code

The code below. There is room for improvement because my solution uses three arguments in vain.

N, X = map(int, input().split())
patty = [1]
buns = [0]

for i in range(0, N):
    patty.append(patty[i] * 2 + 1)
    buns.append(buns[i] * 2 + 2)

print(patty)
print(buns)

burger_high = patty[N] + buns[N]
print("burger : ", burger_high)
print("burger/2 : ", burger_high/2)


def dfs(now_runrun, now_burger_high, dimension):
    if dimension == 0:
        return 1
    ##If Runrun is at the bottom, you can't eat any patties
    elif now_runrun == 1:
        return 0

    ##If Runrun is in the middle, n-1D burger+Eat 1
    elif now_runrun == now_burger_high // 2 + 1:
        return patty[dimension - 1] + 1

    ##Eat all patties when Runrun is at the top
    elif now_runrun == now_burger_high:
        return patty[dimension]


    next_burger = now_burger_high // 2 - 1
    next_dimension = dimension - 1

    if now_runrun <= now_burger_high // 2:
        return dfs(now_runrun - 1, next_burger, next_dimension)
    else:
        return dfs(now_runrun - (patty[next_dimension] + buns[next_dimension] + 2),
                   next_burger, next_dimension) + patty[next_dimension] + 1


print(dfs(X, burger_high, N))