Algoogle

Algorithm for Programming Contest

AOJ 0503 Cup

Category: AOJ Tag: math

Cup

問題概要


カップを円盤に見立てたハノイの塔の初期状態が与えられる(塔は左から順にABC).
移動可能な各カップは1ステップで左右どちらか1つ分しか移動できない(AからCなどの移動は不可能). この状態からm回以内にAに全てのカップがあるかCに全てのカップがあるかの状態にしたい.
最小のステップを求めよ.

解法


Aに全てのカップがある場合とCに全てのカップがある場合を初期状態としてもよい.
このとき一番小さいカップから目的の位置に移動させることを考える.
Aから一番小さいカップiを移動させるには上の他のカップをCに移動させ, そのあとiをBに移動する.
これに必要なステップ数は上に載ってる数をkとすると.
さらにBからCに移動させるにはさっきCに移動させたカップをAに戻して, iをBからCに移動する.
このステップ数は対称な動きをしているので上と同じ.

移動の方法はこれだけなので, 現在より大きいカップは常に全てAかCにまとまっている.
よってこれをカップの小さい順に繰り返せば求めたい回数が計算できる.

コード


(0503.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> tr;

int pow3(int k)
{
        int ret = 1, x = 3;
        for (int i = 0; i < k; i++) ret *= x;
        return ret;
}

long long solver(vector<int> st)
{
        long long ret = 0;
        for (int i = 0; i < n; i++) {
                if(st == tr) return ret;
                int np = 0, p = 0, mp = 0;
                for (int j = 0; j < 3; j++) {
                        if(st[j]&(1<<i)) p = j;
                        if(tr[j]&(1<<i)) np = j;
                }
                if(p == np) continue;
                mp = (7^(1<<p|1<<np))>>1;
                int up = st[p]&(~((1<<(i+1))-1));
                st[p] ^= 1<<i;
                if(abs(np-p)==1){
                        st[mp] |= up;
                        st[p] ^= up;
                }
                st[np] |= 1<<i;
                ret += abs(np-p)*pow3(__builtin_popcount(up));
                if(ret > m) return ret;
        }
        return ret;
}

int solve()
{
        vector<int> st(3);
        st[0] = (1<<n)-1;
        long long ans = solver(st);
        swap(st[0],st[2]);
        ans = min(ans, solver(st));
        return ans > m? -1: ans;
}

bool input()
{
        cin >> n >> m;
        if(!n and !m) return 0;
        tr.clear();
        tr.resize(3);
        for (int i = 0; i < 3; i++) {
                int k; cin >> k;
                for (int j = 0; j < k; j++) {
                        int t; cin >> t;
                        tr[i] |= 1<<(t-1);
                }
        }

        return 1;
}

int main()
{
        while(input()) cout << solve() << endl;
        return 0;
}

Comments