### PROBLEM LINK:

**Author:** Dr. M Kaykobad

**Tester:** Jingbo Shang

**Editorialist:** Jingbo Shang

### DIFFICULTY:

Easy – Medium

### PREREQUISITES:

Dynamic Programming

### PROBLEM:

Given a method to solve the p-peg Hanoi Towers of n plates, determine after how many steps should be done in the optimal solution before the k-th smallest plate is placed in its final position.

### EXPLANATION:

First of all, we can calculate the optimal steps needed for (n,p) system, following the formula stated in the description:

Then, we can calculate the answer by adding a dimension:

Therefore, we can get the answer in O(NPK) time for all answer. Note that we need using long long to store our answer here.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.