Here we have made your task little bit difficult by making the problem more flexible. Here the disks can be in any peg initially.

If more than one disk is in a certain peg, then they will be in a valid arrangement (larger disk will not be on smaller ones). We will give you two such arrangements of disks. You will have to find out the minimum number of moves, which will transform the first arrangement into the second one. Of course you always have to maintain the constraint that smaller disks must be upon the larger ones.

## Input

The input file contains at most 100 test cases. Each test case starts with a positive integer N ( 1N60), 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 12 or 3. If the i-th ( 1iN) 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 specified in the problem statement.

```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```

代码：

``` 1 #include<cstdio>
2 const int maxn =70;
3 int n,start[maxn],finish[maxn];
4 long long Func(int *p,int i,int final)
5 {
6     if(i==0) return 0;
7     if(p[i]==final) return Func(p,i-1,final);
8     return Func(p,i-1,6-p[i]-final)+(1LL<<(i-1));
9 }
10 int main()
11 {
12     int kase=0;
13     while(scanf("%d",&n)==1&&n)
14     {
15       for(int i=1;i<=n;i++)
16             scanf("%d",&start[i]);
17       for(int i=1;i<=n;i++)
18           scanf("%d",&finish[i]);
19       int k=n;
20       while(k>=1 && start[k]==finish[k])k--;
21
22       long long ans=0;
23       if(k>=1)
24       {
25           int other=6-start[k]-finish[k];
26           ans =Func(start,k-1,other)+Func(finish,k-1,other)+1;
27       }
28       printf("Case %d: %lld\n",++kase,ans);
29     }
30 }```

Problem setter: Md. Kamruzzaman

Special Thanks: Derek Kisman (Alternate Solution), Shahriar Manzoor (Picture Drawing)

Miguel Revilla 2004-12-10

657 篇文章64 人订阅

0 条评论

## 相关文章

12920

7710

14300

11910

27560

### Tour UVA - 1347

John Doe, a skilled pilot, enjoys traveling. While on vacation, he rents a small...

35950

30420

9530

### 3097: Hash Killer I

3097: Hash Killer I Time Limit: 5 Sec  Memory Limit: 128 MBSec  Special Judge Su...

24340

28150