【题解】UVa 10795【A Different Task】

背景

汉诺塔的推广问题

分析

考虑编号最大的盘子,如果这个盘子在初始局面和目标局面中处于同一根柱子上面,那么很显然就不需要移动了。这样,就可以在初始局面和目标局面中,找出所在柱子不同的盘子编号最大的那一个,设为$k$,那么$k$必须移动。
首先,考虑需要移动的编号为$K$最大的盘子。将$K-1$的盘子移动到不是目标也不是起始的那根柱子上,成为参考局面。
让起始状态和目标状态都变成参考局面,然后步数就是两者相加再加1,加1是由于还要把第K个盘子移到目标柱子上。
中转的柱子编号为$6 – start – finish$,$6$是由于$1+2+3 = 6$。
在递归的过程中,如果$s[i] == $中转的柱子的话就将继续比较前一个是不是也在中转柱子上,否则,就应该前$K-1$个盘子移动到$6 -$当前在的柱子$-$中转的柱子的那根柱子上,然后把盘子$K$移动到中转的柱子上后,再将前$k-1$个盘子移到中转的柱子上,根据汉诺塔问题的经典结论,这需要$2^{i – 1} – 1$步,加上移动$K$的那一步刚好是$2^{i – 1}$步。
注意:需要用到$int64$因为$n \leq 60$而上面提到的$2^{i -1}$就非常大了。

代码

#include<cstdio>

typedef long long int64;

int64 f(int *P,int i,int final){
    if(i == 0) return 0;
    if(P[i] == final) return f(P,i - 1,final);
    return f(P,i - 1,6 - P[i] - final) + (1LL << (i - 1));
}

const int MAXN = 60 + 6;
int n,start[MAXN],finish[MAXN];

int main(){
    int id = 0;
    while(scanf("%d",&n) == 1 && n){
        for(int i = 1;i <= n;i++) scanf("%d",&start[i]);
        for(int i = 1;i <= n;i++) scanf("%d",&finish[i]);
        int k = n;
        while(k >= 1 && start[k] == finish[k]) k--;
        int64 ans = 0;
        if(k >= 1){
            int other = 6 - start[k] - finish[k];
            ans = f(start,k - 1,other) + f(finish,k - 1,other) + 1;
        } 
        printf("Case %d: %lld\n",++id,ans);
    }

    return 0;
}