0
Your rating: None

CodeChef submission 83952 (C++ 4.0.0-8)

CodeChef submission 83952 (C++ 4.0.0-8) plaintext list. Status: TLE, problem G1, contest SEP09. By gmark (Mark Greve), 2009-09-01 23:22:25.
  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.  
  33. int grundy(int x) {
  34. 	if (x==0) return 0;
  35. 	int& ref = dp[k][x];
  36. 	if (ref != -1) return ref;
  37. 	set<int> seen;
  38. 	for (int m=1;m<=min(x,k);++m) {
  39. 		for (int i=0;x-m-i>=0;++i) {
  40. 			int ns = grundy(i) ^ grundy(x-m-i);
  41. 			seen.insert(ns);
  42. 		}
  43. 	}
  44. 	for (int i=0;;++i) if (!seen.count(i)) return ref = i;
  45. }
  46.  
  47. int numf[2001];
  48. char s[2005];
  49. char os[2005];
  50.  
  51. bool determine_winner() {
  52. 	int cur = 0, ret = 0;
  53. 	for (int i=0;i<=n;++i) {
  54. 		if (i==n || s[i]=='0') {
  55. 			ret ^= grundy(cur);
  56. 			cur = 0;
  57. 		}
  58. 		else ++cur;
  59. 	}
  60. 	return ret != 0;
  61. }
  62.  
  63.  
  64. int main() {
  65. 	memset(dp,-1,sizeof dp);
  66. 	int NCASES;
  67. 	scanf("%d", &NCASES);
  68. 	while (NCASES-- > 0) {
  69. 		scanf("%d %d", &n, &k);
  70. 		scanf("%s", s);
  71. 		strcpy(os,s);
  72.  
  73. 		for (int i=0;i<n;++i) numf[i] = 0;
  74. 		for (int i=n-1;i>=0;--i) {
  75. 			if (i==n-1) numf[i] = (s[i]=='1');
  76. 			else numf[i] = (s[i]=='0' ? 0 : 1 + numf[i+1]);
  77. 		}
  78. 			
  79. 		int win = determine_winner();
  80. 		if (!win) printf("Johnny wins\n");
  81. 		else {
  82. 			printf("Mary wins\n");
  83. 			bool f = 0;
  84. 			for (int m=k;m>=1 && !f;--m) {
  85. 				for (int p=0;p<n-m+1;++p) if (numf[p]>=m) {
  86. 					for (int j=p;j<p+m;++j) s[j] = '0';
  87. 					if (!determine_winner()) {
  88. 						printf("%s\n", s);
  89. 						f = 1;
  90. 						break;
  91. 					}
  92. 					for (int j=p;j<p+m;++j) s[j] = os[j];
  93. 				}
  94. 			}
  95. 		}
  96. 		cout << endl;
  97. 	}
  98. }
  99.

Comments