fork download
copy 
  1. /*
  2.  * cd.cpp
  3.  *
  4.  *  Created on: 2012-6-25
  5.  *      Author: mac
  6.  */
  7. #include <cstdio>
  8. #include <cstring>
  9. #include <algorithm>
  10. #include <iostream>
  11. #include <climits>
  12. #include <numeric>
  13. #include <string>
  14. #include <cassert>
  15. #define foreach(e,x) for(__typeof(x.begin()) e=x.begin();e!=x.end();++e)
  16. #define REP(i,n) for(int i=0;i<n;++i)
  17. using namespace std;
  18.  
  19. //2,3,...,A
  20.  
  21. struct Card {
  22. 	int p, r;
  23. 	Card() {
  24. 	}
  25. 	Card(int p, int r) {
  26. 		this->p = p;
  27. 		this->r = r;
  28. 	}
  29. 	bool operator<(const Card&o) const {
  30. 		return p != o.p ? p < o.p : r < o.r;
  31. 	}
  32.  
  33. 	int id() {
  34. 		return (p - 2) * 4 + r;
  35. 	}
  36.  
  37. 	void read() {
  38. 		cin >> p >> r;
  39. 		if (p == 1)
  40. 			p = 14;
  41. 		r = 4 - r;
  42. 	}
  43. };
  44.  
  45. void show(int who) {
  46. 	for (int i = 0; i < 5; ++i) {
  47. 		cout << who % 52 << " ";
  48. 		who /= 52;
  49. 	}
  50. 	cout << endl;
  51. }
  52.  
  53. struct Hand {
  54. 	int type, dot, col, who;
  55. 	Hand() {
  56. 	}
  57. 	Hand(int type, int dot, int col, int who) {
  58. 		this->type = type;
  59. 		this->dot = dot;
  60. 		this->col = col;
  61. 		this->who = who;
  62. 	}
  63.  
  64. 	bool operator<(const Hand&o) const {
  65. 		if (type != o.type)
  66. 			return type > o.type;
  67. 		if (dot != o.dot)
  68. 			return dot < o.dot;
  69. 		if (col != o.col)
  70. 			return col < o.col;
  71. 		return false;
  72. 	}
  73. };
  74.  
  75. Card cards[5];
  76.  
  77. bool isStright(int&dot, int&col) {
  78. 	bool ok = true;
  79. 	for (int i = 1; i < 5; ++i) {
  80. 		if (cards[i].p != cards[0].p + i)
  81. 			ok = false;
  82. 	}
  83. 	if (ok) {
  84. 		dot = cards[0].p, col = 0;
  85. 		for (int i = 5 - 1; i >= 0; --i) {
  86. 			col = col * 4 + cards[i].r;
  87. 		}
  88. 		return true;
  89. 	}
  90.  
  91. 	//check A2345
  92. 	if (cards[4].p == 14) {
  93. 		ok = true;
  94. 		for (int i = 0; i < 4; ++i) {
  95. 			if (cards[i].p != i + 2)
  96. 				ok = false;
  97. 		}
  98. 		if (ok) { //good! A2345
  99. 			dot = 1, col = 0;
  100. 			for (int i = 4 - 1; i >= 0; --i) {
  101. 				col = col * 4 + cards[i].r;
  102. 			}
  103. 			col = col * 4 + cards[4].r;
  104. 			return true;
  105. 		}
  106. 	}
  107.  
  108. 	return false;
  109. }
  110.  
  111. bool isFlush() {
  112. 	for (int i = 1; i < 5; ++i) {
  113. 		if (cards[i].r != cards[0].r)
  114. 			return false;
  115. 	}
  116. 	return true;
  117. }
  118.  
  119. string makeIt(int&dot, int&col) {
  120. 	pair<int, Card> ps[5];
  121. 	string cnt = "";
  122. 	for (int i = 0, j; i < 5; i = j) {
  123. 		for (j = i; j < 5 && cards[j].p == cards[i].p; ++j)
  124. 			;
  125. 		cnt += char('0' + j - i);
  126. 		for (int k = i; k < j; ++k) {
  127. 			ps[k] = make_pair(j - i, cards[k]);
  128. 		}
  129. 	}
  130. 	sort(ps, ps + 5);
  131.  
  132. 	dot = col = 0;
  133.  
  134. 	for (int i = 5 - 1; i >= 0; --i) {
  135. 		dot = dot * 13 + ps[i].second.p - 2;
  136. 		col = col * 4 + ps[i].second.r;
  137. 	}
  138.  
  139. 	sort(cnt.rbegin(), cnt.rend());
  140. 	return cnt;
  141. }
  142.  
  143. void makeItSorted(int&dot, int&col) {
  144. 	dot = 0, col = 0;
  145. 	for (int i = 5 - 1; i >= 0; --i) {
  146. 		dot = dot * 13 + cards[i].p - 2;
  147. 		col = col * 4 + cards[i].r;
  148. 	}
  149. }
  150.  
  151. Hand process() {
  152. 	sort(cards, cards + 5);
  153. 	int dot, col, who = 0;
  154.  
  155. 	for (int i = 0; i < 5; ++i) {
  156. 		who = who * 52 + cards[i].id();
  157. 	}
  158.  
  159. 	bool isS = isStright(dot, col);
  160. 	bool isF = isFlush();
  161. 	int type;
  162.  
  163. 	int dotG, colG;
  164. 	string cnt = makeIt(dotG, colG);
  165.  
  166. 	if (isS && isF) {
  167. 		type = 1;
  168. 		return Hand(type, dot, col, who);
  169. 	}
  170.  
  171. 	if (cnt == "41") {
  172. 		type = 2;
  173. 		return Hand(type, dotG, colG, who);
  174. 	}
  175.  
  176. 	if (cnt == "32") {
  177. 		type = 3;
  178. 		return Hand(type, dotG, colG, who);
  179. 	}
  180.  
  181. 	int dotS, colS;
  182. 	makeItSorted(dotS, colS);
  183.  
  184. 	if (isF) {
  185. 		type = 4;
  186. 		return Hand(type, dotS, colS, who);
  187. 	}
  188.  
  189. 	if (isS) {
  190. 		type = 5;
  191. 		return Hand(type, dot, col, who);
  192. 	}
  193.  
  194. 	if (cnt == "311") {
  195. 		type = 6;
  196. 		return Hand(type, dotG, colG, who);
  197. 	}
  198.  
  199. 	if (cnt == "221") {
  200. 		type = 7;
  201. 		return Hand(type, dotG, colG, who);
  202. 	}
  203.  
  204. 	if (cnt == "2111") {
  205. 		type = 8;
  206. 		return Hand(type, dotG, colG, who);
  207. 	}
  208.  
  209. 	type = 9;
  210. 	return Hand(type, dotS, colS, who);
  211. }
  212.  
  213. typedef long long int64;
  214.  
  215. bool myCard[52] = { }, youCard[52] = { };
  216. int n;
  217.  
  218. void readCardSet(int n, bool cardSet[]) {
  219. 	Card c;
  220. 	for (int i = 0; i < n; ++i) {
  221. 		c.read();
  222. 		cardSet[c.id()] = true;
  223. 	}
  224. }
  225.  
  226. Card allCard[52];
  227.  
  228. Card cur[5];
  229.  
  230. const int MAX_HANDS = 3000000 + 10;
  231.  
  232. Hand hands[MAX_HANDS];
  233. int nHands = 0;
  234.  
  235. bool check(int who, bool cardSet[], int n) {
  236. 	int cnt = 0;
  237. 	for (int i = 0; i < 5; ++i) {
  238. 		int x = who % 52;
  239. 		who /= 52;
  240. 		if (cardSet[x])
  241. 			++cnt;
  242. 	}
  243. 	return cnt == n;
  244. }
  245.  
  246. void dfs(int u, int who, int cnt) { //search all cardSet combination
  247. 	if (u == 52) {
  248. 		if (cnt == 5 && (check(who, myCard, n) || check(who, youCard, n - 1))) {
  249. 			memcpy(cards, cur, sizeof cur);
  250. 			hands[nHands++] = process();
  251. 		}
  252. 		return;
  253. 	}
  254. 	dfs(u + 1, who, cnt);
  255. 	if (cnt < 5) {
  256. 		cur[cnt] = allCard[u];
  257. 		dfs(u + 1, who * 52 + u, cnt + 1);
  258. 	}
  259. }
  260.  
  261. bool check(const Hand&h, bool cardSet[], int n) {
  262. 	return check(h.who, cardSet, n);
  263. }
  264.  
  265. typedef long long int64;
  266.  
  267. int64 comb(int n, int m) {
  268. 	int64 ret = 1;
  269. 	for (int i = 0; i < m; ++i) {
  270. 		ret *= n - i;
  271. 		ret /= i + 1;
  272. 	}
  273. 	return ret;
  274. }
  275.  
  276. int id[5];
  277.  
  278. int64 A, B;
  279.  
  280. int dp[6][60]; //rem,max
  281.  
  282. void prepare() {
  283. 	memset(dp, 0, sizeof dp);
  284. 	fill(dp[0], dp[0] + 60, 1);
  285. 	for (int rem = 1; rem <= 5; ++rem) {
  286. 		for (int mx = 1; mx <= 52; ++mx) {
  287. 			dp[rem][mx] += dp[rem][mx - 1] + dp[rem - 1][mx - 1];
  288. 		}
  289. 	}
  290. }
  291.  
  292. int curv[5];
  293. int mp[4000000];
  294.  
  295. int eval(int v[], int n) {
  296. 	int code = 0;
  297. 	for (int i = 0; i < n; ++i) {
  298. 		code += dp[i][52];
  299. 	}
  300. 	for (int i = 0; i < n; ++i)
  301. 		code += dp[n - i][v[i]];
  302. 	return code;
  303. }
  304.  
  305. void dfs1(int u, int cnt) {
  306. 	if (u == 5) {
  307. 		int cd = eval(curv, cnt);
  308. 		A += (cnt % 2 == 0 ? 1 : -1) * mp[cd];
  309. 		return;
  310. 	}
  311. 	dfs1(u + 1, cnt);
  312. 	curv[cnt] = id[u];
  313. 	dfs1(u + 1, cnt + 1);
  314. }
  315.  
  316. void dfs2(int u, int cnt) {
  317. 	if (u == 5) {
  318. 		int cd = eval(curv, cnt);
  319. 		mp[cd]++;
  320. 		return;
  321. 	}
  322. 	dfs2(u + 1, cnt);
  323. 	curv[cnt] = id[u];
  324. 	dfs2(u + 1, cnt + 1);
  325. }
  326.  
  327. int main() {
  328. 	cin >> n;
  329. 	readCardSet(n, myCard);
  330. 	readCardSet(n - 1, youCard);
  331.  
  332. 	for (int i = 2; i <= 14; ++i) {
  333. 		for (int j = 0; j < 4; ++j) {
  334. 			Card c(i, j);
  335. 			allCard[c.id()] = c;
  336. 		}
  337. 	}
  338.  
  339. 	dfs(0, 0, 0);
  340.  
  341. 	sort(hands, hands + nHands);
  342.  
  343. 	int rem = 52 - n - (n - 1);
  344. 	A = 0, B = 1;
  345. 	B *= comb(rem, 5 - n);
  346. 	rem -= 5 - n;
  347. 	B *= comb(rem, 5 - (n - 1));
  348.  
  349. 	prepare();
  350.  
  351. 	for (int i = 0; i < nHands; ++i) {
  352. 		Hand&h = hands[i];
  353. 		if (check(h, myCard, n)) {
  354. 			int who = h.who;
  355. 			for (int j = 0; j < 5; ++j) {
  356. 				id[j] = who % 52;
  357. 				who /= 52;
  358. 			}
  359.  
  360. 			sort(id, id + 5);
  361. 			reverse(id, id + 5);
  362. 			dfs1(0, 0);
  363. 		}
  364.  
  365. 		if (check(h, youCard, n - 1)) {
  366. 			int who = h.who;
  367. 			for (int j = 0; j < 5; ++j) {
  368. 				id[j] = who % 52;
  369. 				who /= 52;
  370. 			}
  371. 			sort(id, id + 5);
  372. 			reverse(id, id + 5);
  373. 			dfs2(0, 0);
  374. 		}
  375. 	}
  376.  
  377. 	int64 G = __gcd(A, B);
  378. 	A /= G, B /= G;
  379. 	cout << A << "/" << B << endl;
  380.  
  381. 	return 0;
  382. }
  383.  
Success #stdin #stdout 0.33s 65376KB
comments (?)
stdin
copy 
5 

2  1

2  2

2  3

2  4

3  1

1  1

1  2

1  3

3  2
stdout
copy 
42/43
https://ideone.com/M1uIV
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!