解題區/解題區 - UVa

UVa 11421 - Arranging Cards

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

把每一種牌當作字串串在一起，請問第 k 小字典順序的排列為何？並且相同數字 (rank) 的牌不能放在一起。

Sample Input

1
2
3
4
5
6
7
8
9
6 1
2S 3S 3C 4S 4C 4D
6 120
2S 3S 3C 4S 4C 4D
6 121
2S 3S 3C 4S 4C 4D
16 654321234567
2S 3S 4S 5S 2C 3C 4C 5C 2D 3D 4D 5D 2H 3H 4H 5H
0 0

Sample Output

1
2
3
4
Case 1: 2S 4C 3C 4D 3S 4S
Case 2: 4S 3S 4D 3C 4C 2S
Case 3: Not found
Case 4: 5D 4S 2D 5H 3S 4H 5S 2H 3D 2C 5C 4D 2S 3C 4C 3H

Solution

題目最麻煩的地方是 k 必須使用 long long 才裝得下，然而中間運算過程中很容易超過 long long 因此在終止條件上會變得很難處理。

首先我們必須要知道那些牌可以排出哪幾種方法，但是很明顯地基礎的 dp 無法用上，少說狀態也必須是 13 * 2^50 之類的玩相鄰不可同色。

因此最後將牌壓縮成，擁有 4 張一樣、3 張、2 張、1 張的個數，擁有多少種排列方式。在寫遞迴的時候，標記上一次使用哪一類型的牌。為了逃出 overflow 的運算，使用一個 double 類別的輔助陣列，同樣計算方法數。

隨後知道固定類型的方法數，依序從字典順序小的開始窮舉是否要擺放於此位置。

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <stdio.h> 
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
int usedg[16][16][16][16][5];
long long dp[16][16][16][16][5];
double dp2[16][16][16][16][5];
const long long MAXVAL = 1e+18 + 10;
long long g(int f4, int f3, int f2, int f1, int last) {
    if (usedg[f4][f3][f2][f1][last])
        return dp[f4][f3][f2][f1][last];
    usedg[f4][f3][f2][f1][last] = 1; 
    long long &ret = dp[f4][f3][f2][f1][last];
    double &ret2 = dp2[f4][f3][f2][f1][last];
    if (f4 + f3 + f2 + f1 == 0) {
        ret = 1;
        ret2 = 1;
        return 1;
    }
    if (f4 > 0) {
        ret += 4 * f4 * g(f4-1, f3+1, f2, f1, 4);
        ret2 += 4 * f4 * dp2[f4-1][f3+1][f2][f1][4];
    }
    ret = min(ret, MAXVAL);
    if (ret2 > MAXVAL)	return ret;
    if (f3 > 0) {
        if (last == 4) {
            ret += 3 * (f3 - 1) * g(f4, f3-1, f2+1, f1, 3);
            ret2 += 3 * (f3 - 1) * dp2[f4][f3-1][f2+1][f1][3];
        } else {
            ret += 3 * (f3) * g(f4, f3-1, f2+1, f1, 3);
            ret2 += 3 * (f3) * dp2[f4][f3-1][f2+1][f1][3];
        }
    }
    ret = min(ret, MAXVAL);
    if (ret2 > MAXVAL)	return ret;
    if (f2 > 0) {
        if (last == 3) {
            ret += 2 * (f2 - 1) * g(f4, f3, f2-1, f1+1, 2);
            ret2 += 2 * (f2 - 1) * dp2[f4][f3][f2-1][f1+1][2];
        } else {
            ret += 2 * (f2) * g(f4, f3, f2-1, f1+1, 2);
            ret2 += 2 * (f2) * dp2[f4][f3][f2-1][f1+1][2];
        }
    }
    ret = min(ret, MAXVAL);
    if (ret2 > MAXVAL)	return ret;
    if (f1 > 0) {
        if (last == 2) {
            ret += (f1 - 1) * g(f4, f3, f2, f1-1, 1);
            ret2 += (f1 - 1) * dp2[f4][f3][f2][f1-1][1];
        } else {
            ret += f1 * g(f4, f3, f2, f1-1, 1);
            ret2 += f1 * dp2[f4][f3][f2][f1-1][1];
        }
    }
    ret = min(ret, MAXVAL);
    if (ret2 > MAXVAL)	return ret;
    return ret;
}
int card2Num(char suit, char rank) {
    int s, r;
    switch(suit) {
        case 'S': s = 3;break;
        case 'C': s = 0;break;
        case 'H': s = 2;break;
        case 'D': s = 1;break;
    }
    switch(rank) {
        case '2'...'9': r = rank-'0'-2;break;
        case 'T': r = 12;break;
        case 'J': r = 9;break;
        case 'Q': r = 11;break;
        case 'K': r = 10;break;
        case 'A': r = 8;break;
    }
    return r * 4 + s;
}
int main() {
    int cases = 0;
    int N;
    long long K;
    char psuit[] = "CDHS", prank[] = "23456789AJKQT";
    while (scanf("%d %lld", &N, &K) == 2) {
        if (N == 0 && K == 0)
            break;
        char card[10];
        int A[64];
        for (int i = 0; i < N; i++) {
            scanf("%s", card);
            int x = card2Num(card[1], card[0]);
            A[i] = x;
        }
        printf("Case %d:", ++cases);
        int ret[64];
        int NOT_FOUND = 0; 
        K--;
        for (int i = 0; i < N; i++) {
            sort(A+i, A+N);
            ret[i] = -1;
            for (int j = i; j < N; j++) {
                int ch = A[j];
                int cnt[13] = {}, f[8] = {};
                if (i && ch/4 == ret[i-1]/4) 
                    continue;
                for (int k = i; k < N; k++)
                    cnt[A[k]/4]++;
                int last = cnt[ch/4]--;
                for (int k = 0; k < 13; k++)
                    f[cnt[k]]++;
                long long way = g(f[4], f[3], f[2], f[1], last);			
//				printf("%d %d %d %d - %d %lld\n", f[4], f[3], f[2], f[1], last, way);
//				printf("%lld %lf\n", way, dp2[f[4]][f[3]][f[2]][f[1]][last]);
                if (dp2[f[4]][f[3]][f[2]][f[1]][last] > K) {
                    swap(A[i], A[j]);
                    ret[i] = ch;
                    break;
                } else {
                    K -= way;
                }
            }
            if (ret[i] == -1) {
                NOT_FOUND = 1;
                break;
            }
//			puts("------");
        }
        if (NOT_FOUND) {
            puts(" Not found");
            continue;
        }
        for (int i = 0; i < N; i++)  {
//			printf("%d\n", ret[i]);
            printf(" %c%c", prank[ret[i]/4], psuit[ret[i]%4]);
        }
        puts("");
    }
    return 0;
}
/*
50 1
2C 2D 2H 2S
3C 3D 3H 3S
4C 4D 4H 4S
5C 5D 5H 5S
6C 6D 6H 6S
7C 7D 7H 7S
8C 8D 8H 8S
9C 9D 9H 9S
TC TD TH TS
JC JD JH JS
QC QD QH QS
KC KD KH
AC AD AH
*/