P15855 [Lanquiao Cup 2nd International Contest] Tower of Hanoi Problem

The Tower of Hanoi is a classic math problem. Given three pegs A, B, and C, peg A has $n$ disks of different sizes stacked in order, with the largest at the bottom and the smallest at the top. Now you need to move all disks from peg A to peg C. What is the minimum number of moves required? The minimum number of moves is $2^n - 1$. Moreover, if you must finish in the minimum number of moves, there is only one possible sequence of moves. For example, when $n = 3$, you need a total of $7$ moves: Move $1$: move the smallest disk from A to C, written as A->C; Move $2$: move the 2nd smallest disk from A to B, written as A->B; Move $3$: move the smallest disk from C to B, written as C->B; Move $4$: move the 3rd smallest disk from A to C, written as A->C; Move $5$: move the smallest disk from B to A, written as B->A; Move $6$: move the 2nd smallest disk from B to C, written as B->C; Move $7$: move the smallest disk from A to C, written as A->C. Now, between move $x$ and move $y$, how many times does A->B occur, how many times does A->C occur, how many times does B->A occur, how many times does B->C occur, how many times does C->A occur, and how many times does C->B occur?

The first line contains an integer $n$. The second line contains two integers $x, y$, separated by a space.

Output six lines, each containing one integer, representing the answers to the six questions above.

### Constraints For $30\%$ of the testdata, $1 \le n \le 10$, $1 \le x \le y \le 2^n - 1$. For $60\%$ of the testdata, $1 \le n \le 30$, $1 \le x \le y \le 2^n - 1$. For all testdata, $1 \le n \le 100$, $1 \le x \le y \le 2^n - 1$, and $y \le 10^{18}$. Translated by ChatGPT 5