UVA

Input

The input le contains at most 100 test cases. Each test case starts with a positive integer N (1 ≤
N ≤ 60), which means the number of disks. You will be given the arrangements in next two lines. Each
arrangement will be represented by N integers, which are 1, 2 or 3. If the i-th (1 ≤ i ≤ N) integer is
1, you should consider that i-th disk is on Peg-A. Input is terminated by N = 0. This case should not
be processed.
Output
Output of each test case should consist of a line starting with `Case #: ' where # is the test case
number. It should be followed by the minimum number of moves as specied in the problem statement.
Sample Input
3
1 1 1
2 2 2
3
1 2 3
3 2 1
4
1 1 1 1
1 1 1 1
0
Sample Output
Case 1: 7
Case 2: 3
Case 3: 0

#include <cstdio>

using namespace std;

int A[70], B[70];

long long int f(int *A, int i, int x);

int main() {
    int n, t = -1;
    for (int base = 1; scanf("%d", &n) && n; t = -1) {
        for (int i = 0; i < n; ++i) {
            scanf("%d", A + i);
        }
        for (int i = 0; i < n; ++i) {
            scanf("%d", B + i);
            if (A[i] != B[i])
                t = i;
        }
        int x = 6 - A[t] - B[t];
        printf("Case %d: %lld
", base++, t == -1 ? 0 : (f(A, t - 1, x) + f(B, t - 1, x) + 1));
    }
}

long long f(int *A, int i, int x) {
    if (i < 0)
        return 0;
    if (A[i] == x)
        return f(A, i - 1, x);
    return f(A, i - 1, 6 - x - A[i]) + (1LL << i);  //这里1LL要注意了
}