解題區►解題區 - UVa

UVa 12806 - Grand Tichu

contents

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

Problem

增加 4 張牌到撲克牌中，每名玩家將會獲得 14 張牌，而在有 8 張的時候，可以預估是否會湊到 4 種類型的手牌，如果可以組合出其中一種的機率大於 0.25，則喊出 Grand Tichu!。

Sample Input

1
2
3
4
5
6
7
D23468AA
D2P4688K
D23468KA
D2233889
PdM2345T
PdM234AA
0

Sample Output

1
2
3
4
5
6
Grand Tichu!
Grand Tichu!
Grand Tichu!
...
...
...

Solution

搜索順序的重要性，由於 4 種組合牌中，只與 ADPMd 有關，剩下的類型可以直接利用組合去計算，只要窮舉 ADPMd 出現在手牌的組合情況即可。

如果按照一般的 23456789TJQKADPMd 效率不彰，耗費時間太久，再多剪枝都不夠。

一開始誤以為是 4 種機率加總大於 0.25 就輸出，不管怎麼樣連範測都會錯，後來發現是湊出其中一種的機率必須大於 0.25。

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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
long long C[50][50];
const char kind[20] = "ADPMd23456789TJQK";
int ihand[20], ohand[20], mhand[20];
int suffix[20];
long long va[10], vb;
void dfs(int idx, int card, long long ways) {
	if (idx > 4) {
		ways = ways * C[suffix[idx]][14 - card];
		int hh = 0;
		if (ohand[1] > 0 && ohand[2] > 0 && ohand[0] > 0)
			hh = 1, va[hh] += ways;// D P A
		if (ohand[1] > 0 && ohand[0] >= 2)
			hh = 2, va[hh] += ways;// D A A
		if (ohand[2] > 0 && ohand[0] >= 3)
			hh = 3, va[hh] += ways; // P A A A
		if (ohand[1] > 0 && ohand[2] > 0 && ohand[3] > 0 && ohand[4] > 0)
			hh = 4, va[hh] += ways; // D P M d
		vb += ways;
		return ;
	}
	if (card == 14) {
		int hh = 0;
		if (ohand[1] > 0 && ohand[2] > 0 && ohand[0] > 0)
			hh = 1, va[hh] += ways;// D P A
		if (ohand[1] > 0 && ohand[0] >= 2)
			hh = 2, va[hh] += ways;// D A A
		if (ohand[2] > 0 && ohand[0] >= 3)
			hh = 3, va[hh] += ways; // P A A A
		if (ohand[1] > 0 && ohand[2] > 0 && ohand[3] > 0 && ohand[4] > 0)
			hh = 4, va[hh] += ways; // D P M d
		vb += ways;
		return ;
	}
	if (idx == 17 || card + suffix[idx] < 14)	return ;
	for (int i = 0; i <= ihand[idx] && card + i <= 14; i++) {
		ohand[idx] += i;
		dfs(idx+1, card + i, ways * C[ihand[idx]][i]);
		ohand[idx] -= i;
	}
}
int main() {
	for (int i = 0; i < 50; i++) {
		C[i][0] = 1;
		for (int j = 1; j <= i; j++)
			C[i][j] = C[i-1][j-1] + C[i-1][j];
	}
	char hand[64];
	while (scanf("%s", &hand) == 1 && hand[0] != '0') {
		memset(ihand, 0, sizeof(ihand));
		memset(ohand, 0, sizeof(ohand));
		for (int i = 4; i < 17; i++)
			ihand[i] = 4, mhand[i] = 4;
		ihand[0] = 4, mhand[0] = 4;
		for (int i = 1; i <= 4; i++)
			ihand[i] = 1, mhand[i] = 1;
		for (int i = 0; i < 8; i++) {
			int p = find(kind, kind + 17, hand[i]) - kind;
			ihand[p]--, ohand[p]++;
		}
		memset(suffix, 0, sizeof(suffix));
		for (int i = 17; i >= 0; i--)
			suffix[i] = suffix[i+1] + ihand[i];
		memset(va, 0, sizeof(va));
		vb = 0;
		dfs(0, 8, 1);
		int ok = 0;
		for (int i = 0; i < 4; i++) {
			double p = (double)va[i] / vb;
			if (p > 0.25)	ok = 1;
		}
		if (ok)
			puts("Grand Tichu!");
		else
			puts("...");
	}
	return 0;
}
/*
D23468AA
D2P4688K
D23468KA
D2233889
PdM2345T
PdM234AA
0
D23468AA
0.000000
0.125000
1.000000
0.025439
Grand Tichu
D2P4688K
0.000000
0.424761
0.070768
0.004394
Grand Tichu
D23468KA
0.000000
0.125000
0.336263
0.003315
Grand Tichu
D2233889
0.000000
0.046558
0.070768
0.000298
...
PdM2345T
0.000000
0.046558
0.006332
0.004394
...
PdM234AA
0.000000
0.125000
0.125000
0.236702
...
*/