0
Your rating: None

CodeChef submission 64039 (C++ 4.0.0-8)

CodeChef submission 64039 (C++ 4.0.0-8) plaintext list. Status: AC, problem F2, contest AUG09. By gmark (Mark Greve), 2009-08-04 12:49:02.
  1. // Bytelandian Robots
  2. // Source: CodeChef August 2009 Algorithm Challenge
  3. // CodeChef ID: F2
  4. // Date: 02-08-2009
  5. // Author: Mark Greve
  6.  
  7. #include <algorithm>
  8. #include <bitset>
  9. #include <cassert>
  10. #include <cctype>
  11. #include <cmath>
  12. #include <cstdio>
  13. #include <cstdlib>
  14. #include <cstring>
  15. #include <ctime>
  16. #include <deque>
  17. #include <functional>
  18. #include <iomanip>
  19. #include <iostream>
  20. #include <list>
  21. #include <map>
  22. #include <numeric>
  23. #include <queue>
  24. #include <set>
  25. #include <sstream>
  26. #include <stack>
  27. #include <string>
  28. #include <utility>
  29. #include <vector>
  30. using namespace std;
  31.  
  32. typedef long long LL;
  33. const int MOD = 7051954;
  34.  
  35. char s[100000];
  36. int N,L,A,B;
  37. const int MAX=1001;
  38. int nm[MAX], np[MAX];
  39. int dp[MAX][2*MAX+5][3];
  40.  
  41. const int PLUS=0, MINUS=1,NONE=2;
  42.  
  43. int go(int,int);
  44. int go2(int,int,int);
  45.  
  46. bool ok(int d) { return !(A+d>L || A+d<0); }
  47.  
  48. int go2(int at, int d, int next) {
  49. 	if (A+d<B && A+d+(N-at)<B) return 0; // pruning
  50. 	if (A+d>B && A+d-(N-at)>B) return 0; // pruning
  51.  
  52. 	if (next==NONE) return d==B-A;
  53. 	int& ref = dp[at][d+N][next];
  54. 	if (ref!=-1) return ref;
  55. 	ref = 0;
  56. 	if (next==PLUS  && np[at]!=-1) ref=go(np[at]+1, d+1);
  57. 	if (next==MINUS && nm[at]!=-1) ref=go(nm[at]+1, d-1);
  58. 	return ref;
  59. }
  60.  
  61. int go(int at, int d) {
  62. 	if (!ok(d)) return 0;
  63. 	int res = 0;
  64. 	res = res + go2(at,d,PLUS);  if (res>=MOD) res -= MOD;
  65. 	res = res + go2(at,d,MINUS); if (res>=MOD) res -= MOD;
  66. 	res = res + go2(at,d,NONE);  if (res>=MOD) res -= MOD;
  67. 	return res;
  68. }
  69.  
  70. int main() {
  71. 	int NCASES;
  72. 	scanf("%d", &NCASES);
  73. 	while (NCASES-- > 0) {
  74. 		scanf("%d %d %d %d", &N, &L, &A, &B);
  75. 		scanf("%s", s);
  76. 		for (int i=0;i<N;++i) assert(s[i]=='-' || s[i]=='+');
  77. 		int curp = -1, curm = -1;
  78. 		np[N]=nm[N]=-1;
  79. 		for (int i=N-1;i>=0;--i) {
  80. 			if (s[i]=='+') curp = i;
  81. 			if (s[i]=='-') curm = i;
  82. 			nm[i] = curm;
  83. 			np[i] = curp;
  84. 		}
  85.  
  86. 		for (int i=0;i<N;++i)
  87. 			for (int j=0;j<=2*N;++j)
  88. 				dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = -1;
  89.  
  90. 		printf("%d\n", go(0,0));
  91. 	}
  92. }
  93.

Comments