0
Your rating: None

CodeChef submission 82797 (C++ 4.0.0-8)

CodeChef submission 82797 (C++ 4.0.0-8) plaintext list. Status: AC, problem E5, contest . By naughty (Yash), 2009-08-31 18:45:27.
  1.  
  2. /* Author :: Yash */
  3. #include <vector>
  4. #include <list>
  5. #include <cassert>
  6. #include <sstream>
  7. #include <map>
  8. #include <set>
  9. #include <climits>
  10. #include <deque>
  11. #include <fstream>
  12. #include <stack>
  13. #include <bitset>
  14. #include <stack>
  15. #include <queue>
  16. #include <algorithm>
  17. #include <functional>
  18. #include <numeric>
  19. #include <cstring>
  20. #include <utility>
  21. #include <sstream>
  22. #include <iostream>
  23. #include <iomanip>
  24. #include <cstdio>
  25. #include <cmath>
  26. #include <cstdlib>
  27. #include <ctime>
  28. using namespace std;
  29.  
  30. template<class A, class B> A cvt(B x) {stringstream s;s<<x;A r;s>>r;return r;}
  31.  
  32. #define FOR(i,a,b) for(int i= (int )a ; i < (int )b ; ++i) 
  33. #define REP(i,n) FOR(i,0,n)
  34. #define PB push_back
  35. #define PP pop()
  36. #define EM empty()
  37. #define INF 1000000000
  38. #define PF push_front
  39. #define ALL(x) x.begin(),x.end()
  40. #define SORT(x) sort(ALL(x))
  41. #define V(x) vector< x >
  42. #define Debug false
  43. #define PRINT(x)        cout << #x << " " << x << endl
  44. #define LET(x,a) 	    __typeof(a) x(a)
  45. #define IFOR(i,a,b) 	for(LET(i,a);i!=(b);++i)
  46. #define EACH(it,v)  	IFOR(it,v.begin(),v.end())
  47. #define PRESENT(c,x) 	((c).find(x) != (c).end())
  48. #define SZ(x) 		x.size();
  49. #define CPRESENT(c,x) 	(find(c.begin(),c.end(),x) != (c).end())
  50. #define D(N) 		int N
  51. #define S(N)		scanf("%d",&N)
  52.  
  53. typedef pair<int,int>  PI;
  54. typedef pair<int,PI>   TRI;
  55. typedef V( int )       VI;
  56. typedef V( PI  )       VII;
  57. typedef V( string )    VS;
  58. typedef long long      LL;
  59.  
  60. LL C[100][100];
  61.  
  62. void pre() {
  63.  
  64. 	memset(C,0,sizeof C);
  65. 	REP(i,100) C[i][0] = 1;
  66. 	FOR(i,1,100) FOR(j,1,100) C[i][j] = C[i-1][j] + C[i-1][j-1];
  67. }
  68.  
  69. void Ans(int n,int k) {
  70.  
  71. 	assert(n >= k);
  72. 	printf("%lld\n",((C[(n<<1)-k][n-k])*(k+1))/(n+1));
  73. }
  74.  
  75. int main() {
  76.  
  77. 	pre();	
  78. 	int kases; scanf("%d",&kases);
  79. 	while ( kases-- ) {
  80.  
  81. 		int n,m; scanf("%d%d",&n,&m);
  82. 		int a[m];
  83. 		REP(i,m) scanf("%d",&a[i]);
  84. 		
  85. 		bool check = false;
  86. 		REP(i,m) FOR(j,i+1,m) {
  87. 			if ( a[j] < a[i] ) {
  88. 				int cnt = 0;
  89. 				FOR(k,1,a[j]) {
  90. 					REP(l,j) if ( a[l] == k ) ++cnt;
  91. 				}
  92. 				if ( cnt != a[j] - 1 ) { check = true;
  93. 					goto yash;
  94. 				}
  95. 			}
  96. 		}
  97. 		yash:;
  98. 		if ( check ) puts("0");
  99. 		else {
  100. 			int h = *max_element(a,a+m) , p = 0, q = 0;
  101. 			if ( m == 0 ) h = 0;
  102. 			FOR(i,1,n+1) {
  103. 				bool flag = true;
  104. 				REP(j,m) if ( a[j] == i ) flag = false;
  105. 				if ( flag ) {
  106. 					p += ( i < h ) ;
  107. 					q += ( i > h ) ;
  108. 				}
  109. 			}
  110. 			Ans(p+q,p);
  111. 		}
  112. 	}	 
  113. 	return 0;
  114. }
  115.  
  116.  
  117.

Comments