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.

  1. 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))

Recommended Posts

How to solve the recursive function that solved abc115-D
How to make a recursive function
How to create a wrapper that preserves the signature of the function to wrap
Recursive function that displays the XML tree structure [Note]
[Introduction to Python] How to iterate with the range function?
How to hit the document of Magic Function (Line Magic)
How to use the generator
How to call a function
How to use the decorator
How to increase the axis
How to start the program
How to calculate the amount of calculation learned from ABC134-D
How to run the Export function of GCP Datastore automatically
[Introduction to Python] How to get data with the listdir function
How to solve the problem that video content cannot be played on Firefox for Linux
How to calculate the autocorrelation coefficient
How to use the optparse module
How to solve the problem that APL does not start after transferring to the actual device on Kivy-iOS
[Python] How to derive nCk (ABC156-D)
[Python 3.8 ~] How to define a recursive function smartly with a lambda expression
How to solve simultaneous linear equations
The 17th Offline Real-time How to Solve Writing Problems in Python
How to judge that the cross key is input in Python3
How to read the SNLI dataset
How to get the Python version
[Python] How to import the library
[Python] Explains how to use the format function with an example
How to overwrite the output to the console
How to use python zip function
How to use the ConfigParser module
How to use the render function defined in .mako (.html) directly in mako
How to solve the problem that time goes wrong every time you turn on the power in Linux
How to solve slide puzzles and 15 puzzles
Try to solve the function minimization problem using particle swarm optimization
How to deal with the problem that build fails when CI / CD of Python Function with AWS Amplify
The 16th offline real-time how to write problem was solved with Python
How to divide and process a data frame using the groupby function
The 16th offline real-time how to write reference problem to solve with Python
How to use the library "torchdiffeq" that implements Neural ODE's ODE Block
[Python] How to use the enumerate function (extract the index number and element)
[Introduction to Python] How to write a character string with the format function
The 19th offline real-time how to write reference problem to solve with Python
The 15th offline real-time how to write problem was solved with python
[C language] How to use the crypt function on Linux [Password hashing]
How to display the progress bar (tqdm)
How to use the Spark ML pipeline
How to check the version of Django
How to crawl pages that scroll infinitely
How to set the server time to Japanese time
How to manually update the AMP cache
[python] How to use __command__, function explanation
[Linux] How to use the echo command
How to use the Linux grep command
How to get colored output to the console
How to operate Linux from the console
[Python] Understand how to use recursive functions
How to access the Datastore from the outside
How to use the IPython debugger (ipdb)
How to solve the problem that only the process remains when you press cross on the imshow screen of OpenCV
[Circuit x Python] How to find the transfer function of a circuit using Lcapy
How to find the coefficient of the trendline that passes through the vertices in Python