Source code for submission s835

queue.cpp

  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4.  
  5. using namespace std;
  6.  
  7. int dp[600][600];
  8. char people[1042];
  9. int l,lh;
  10.  
  11. void vypis(){
  12. 	for( int i = 0; i <= lh ; i++ )
  13. 	{
  14. 		for( int j = 0; j <= lh; j++ )
  15. 			printf("%d ",dp[i][j]);
  16. 		putchar('\n');
  17. 	} 
  18. }
  19. void solve(){
  20. 	lh = l / 2;
  21. 	for(int i = 0; i <= lh; i++ ){
  22. 		for( int j =0; j <=lh; j++ )
  23. 			dp[i][j] = 0;
  24. 	}
  25. //	for( int i = 0; i <=lh; i++ ){
  26. //		dp[0][i] = 1;
  27. //		dp[i][0] = 1;
  28. //	}
  29. 	dp[0][0] = 1;
  30. //	vypis();
  31. 	int i = 0,j = 0;
  32. 	for( ; i <=lh ; i++ ){
  33. 		for( j = 0; j <= i; j++ ){
  34. 			if(people[i+j]=='.'||people[i+j]=='('){
  35. 				if((i+1)<=lh){
  36. 					dp[i+1][j]+=dp[i][j];
  37. 					dp[i+1][j]%=1000000;
  38. 				}
  39. 			}
  40. 			if(people[i+j]=='.'||people[i+j]==')'){
  41. 				if(((j+1)<=i)){
  42. 					dp[i][j+1]+=dp[i][j];
  43. 					dp[i][j+1]%=1000000;
  44. 				}
  45. 			}
  46. 		}
  47. 	}
  48.  
  49. 	//vypis();
  50. 	printf("%d\n",dp[lh][lh]);
  51. }
  52.  
  53. int main(int argc, char * argv[]){
  54. while(gets(people)){
  55. 	l = strlen(people);
  56. 	solve();
  57. }
  58. return 0;
  59. }
  60.