技巧:
    递归 + 记忆化搜索
思路:
    基于统计的想法出发(可以打破移动顺序)，一共有6中移动方式。 用一个长度为6的数组统计每一个位置需要操作的次数。最后合并求得总答案。
    用数组位置模拟统计的办法主要是为了方便记忆化搜索cache统计和递归函数逻辑闭环。
实现: 
package main

import (
    . "fmt"
    "os"
    "io"
    "bufio"
)
//  0  1  2  3  4  5
// AB AC BA BC CA CB
func getOptIndex(cmd string) int {
    switch cmd {
        case "AB":
        return 0
        case "AC":
        return 1
        case "BA":
        return 2
        case "BC":
        return 3
        case "CA":
        return 4
        case "CB":
        return 5
    }
    return -1
}
// https://ac.nowcoder.com/acm/problem/201839
func NC201839(_r io.Reader, _w io.Writer) {
    in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
    defer out.Flush()
    var n int
    Fscan(in, &n)
    
    cacheMap := make(map[string][6]int)
    
    var hanoi func(int, string, string, string)  [6]int
    hanoi = func(n int, a,b,c string) [6]int{
        if v, ok := cacheMap[Sprintf("%d%s%s%s",n,a,b,c)]; ok {
            return v
        }
        
        optCmd := [6]int{}
        if n == 1 {
            optCmd[getOptIndex(a + c)] += 1
            return optCmd
        }
        a2b := hanoi(n - 1, a, c, b)
        b2a := hanoi(n - 1, b, a, c)
         // merge
        for i := 0; i < 6; i++ {
            optCmd[i] +=a2b[i]
            optCmd[i] +=b2a[i]
        }
        // a2c
        optCmd[getOptIndex(a + c)] += 1
        cacheMap[Sprintf("%d%s%s%s",n,a,b,c)] = optCmd
        return optCmd
    }
   
    optArray := hanoi(n, "A","B","C")
    Fprintf(out, "%s->%s:%d\n", "A","B",optArray[0])
    Fprintf(out, "%s->%s:%d\n", "A","C",optArray[1])
    Fprintf(out, "%s->%s:%d\n", "B","A",optArray[2])
    Fprintf(out, "%s->%s:%d\n", "B","C",optArray[3])
    Fprintf(out, "%s->%s:%d\n", "C","A",optArray[4])
    Fprintf(out, "%s->%s:%d\n", "C","B",optArray[5])
    Fprintf(out, "SUM:%d\n", optArray[0]+optArray[1]+optArray[2]+optArray[3]+optArray[4]+optArray[5])
    
}
func main() {
    NC201839(os.Stdin, os.Stdout)
}