P1760 The Skyward Tower of Hanoi

Direct Path to the Sky Road · Xiao A’s Adventure, Part IV.

With your help, Xiao A has collected valuable data and finally reached the legendary Sky Mountain that connects to the Sky Road. However, there is still some distance to the Sky Road, and Xiao A suddenly realizes he has no map. Fortunately, he finds a treasure chest at the foot of the mountain. Based on experience (does Xiao A even have any?), he judges that the map should be inside. On the chest, there are three pegs and $n$ disks stacked on one peg. After a long time thinking, Xiao A concludes that this is the Tower of Hanoi. Moving takes time, so he must brew a longevity potion to complete the task. Now, he asks you to tell him how many steps are needed, so that he can brew enough potion.

A single integer $n$, the number of disks.

A single integer $s$, the number of steps required.

Constraints For all testdata, $n \le 15000$. Translated by ChatGPT 5