Towers of Hanoi

Lab C Advanced 30 points

Read n (1–6) and print the moves to move n disks from A to C via B, as A -> C, then the number of moves.

Input

One integer.

Output

The moves, then the count.

Example

Input

Output

A -> B
A -> C
B -> C
3

Sample input available Sample output available

Editor

Hints

Move n-1 disks out of the way, move the biggest, then move the n-1 back on top.

Solution explanation

The solution takes 2ⁿ − 1 moves.

Show solution

#include <stdio.h>

int moves = 0;

void hanoi(int n, char from, char via, char to) {
    if (n == 0) return;
    hanoi(n - 1, from, to, via);
    printf("%c -> %c\n", from, to);
    moves++;
    hanoi(n - 1, via, from, to);
}

int main() {
    int n;
    scanf("%d", &n);
    hanoi(n, 'A', 'B', 'C');
    printf("%d\n", moves);
    return 0;
}

Output

Answer