0
Your rating: None

CodeChef submission 83987 (C++ 4.0.0-8)

CodeChef submission 83987 (C++ 4.0.0-8) plaintext list. Status: TLE, problem G1, contest SEP09. By gmark (Mark Greve), 2009-09-02 00:09:35.
  1. // A Bowling Game
  2. // Source: CodeChef September Algorithm Challenge
  3. // CodeChef ID: G1
  4.  
  5. #include <algorithm>
  6. #include <bitset>
  7. #include <cassert>
  8. #include <cctype>
  9. #include <cmath>
  10. #include <cstdio>
  11. #include <cstdlib>
  12. #include <cstring>
  13. #include <ctime>
  14. #include <deque>
  15. #include <functional>
  16. #include <iomanip>
  17. #include <iostream>
  18. #include <list>
  19. #include <map>
  20. #include <numeric>
  21. #include <queue>
  22. #include <set>
  23. #include <sstream>
  24. #include <stack>
  25. #include <string>
  26. #include <utility>
  27. #include <vector>
  28. using namespace std;
  29.  
  30. int dp[21][2001];
  31. int n,k;
  32. int gg[20000];
  33.  
  34. int grundy(int x) {
  35. 	if (x==0) return 0;
  36. 	int& ref = dp[k][x];
  37. 	if (ref != -1) return ref;
  38. 	vector<int> seen;
  39. 	for (int m=1;m<=min(x,k);++m) {
  40. 		for (int i=0;x-m-i>=0;++i) {
  41. 			int ns = grundy(i) ^ grundy(x-m-i);
  42. 			gg[ns] = 1;
  43. 			seen.push_back(ns);
  44. 		}
  45. 	}
  46. 	for (int i=0;;++i) if (gg[i]==0) {
  47. 		for (int i=0;i<seen.size();++i) gg[seen[i]] = 0;
  48. 		return ref = i;
  49. 	}
  50. }
  51.  
  52. char s[2005];
  53. int ng;
  54. int groups[2005];
  55. int sp[2005];
  56.  
  57. void determine_winner() {
  58. 	int ret = 0;
  59. 	for (int i=0;i<ng;++i) {
  60. 		ret ^= grundy(groups[i]);
  61. 	}
  62. 	if (ret==0) {
  63. 		printf("Johnny wins\n");
  64. 		return;
  65. 	}
  66.  
  67. 	printf("Mary wins\n");
  68.  
  69. 	set<int> groups_seen;
  70. 	// Find the best move
  71. 	for (int m=k;m>=1;--m) {
  72. 		for (int i=0;i<ng;++i) if (groups[i]>=m) {
  73. 			if (groups_seen.count(groups[i])) continue;
  74. 			groups_seen.insert(groups[i]);
  75. 			//for (int p=0;p<groups[i]-m+1;++p) {
  76. 			for (int p=0;p<=groups[i]-m-p;++p) {
  77. 				int oret = ret;
  78. 				int nret = ret ^ grundy(groups[i]) ^ grundy(p) ^ grundy(groups[i]-m-p);
  79. 				//printf("\t\t M: %d GROUP %d, CALL on %d and %d\n", m, i, p, groups[i]-m-p);
  80. 				if (nret == 0) {
  81.  
  82. 					//printf("G: %d, P: %d, M: %d, SP: %d\n", i, p, m, sp[i]);
  83. 					for (int j=sp[i] + p; j < sp[i] + p + m; ++j) {
  84. 						//printf("SET %d to 0\n", j);
  85. 						s[j] = '0';
  86. 					}
  87. 					printf("%s\n", s);
  88. 					return;
  89. 				}
  90. 				ret = oret;
  91. 			}
  92. 		}
  93. 	}
  94. }
  95.  
  96.  
  97. int main() {
  98. 	memset(gg,0,sizeof gg);
  99. 	memset(dp,-1,sizeof dp);
  100. 	int NCASES;
  101. 	for (scanf("%d", &NCASES); NCASES-- > 0; ) {
  102. 		scanf("%d %d %s", &n, &k, s);
  103. 		int cur = 0;
  104. 		ng = 0;
  105. 		for (int i=0;i<=n;++i) {
  106. 			if (i==n || s[i]=='0') {
  107. 				groups[ng++] = cur;
  108. 				cur = 0;
  109. 			}
  110. 			else {
  111. 				if (cur==0) sp[ng] = i;
  112. 				++cur;
  113. 			}
  114. 		}
  115. 		determine_winner();
  116. 		printf("\n");
  117. 	}
  118. }
  119.

Comments