fork download
  1. /***********Template Starts Here***********/
  2. #include <bits/stdc++.h>
  3.  
  4. #define pb push_back
  5. #define nl puts ("")
  6. #define sp printf ( " " )
  7. #define phl printf ( "hello\n" )
  8. #define ff first
  9. #define ss second
  10. #define POPCOUNT __builtin_popcountll
  11. #define RIGHTMOST __builtin_ctzll
  12. #define LEFTMOST(x) (63-__builtin_clzll((x)))
  13. #define MP make_pair
  14. #define FOR(i,x,y) for(vlong i = (x) ; i <= (y) ; ++i)
  15. #define ROF(i,x,y) for(vlong i = (y) ; i >= (x) ; --i)
  16. #define CLR(x,y) memset(x,y,sizeof(x))
  17. #define UNIQUE(V) (V).erase(unique((V).begin(),(V).end()),(V).end())
  18. #define MIN(a,b) ((a)<(b)?(a):(b))
  19. #define MAX(a,b) ((a)>(b)?(a):(b))
  20. #define NUMDIGIT(x,y) (((vlong)(log10((x))/log10((y))))+1)
  21. #define SQ(x) ((x)*(x))
  22. #define ABS(x) ((x)<0?-(x):(x))
  23. #define FABS(x) ((x)+eps<0?-(x):(x))
  24. #define ALL(x) (x).begin(),(x).end()
  25. #define LCM(x,y) (((x)/gcd((x),(y)))*(y))
  26.  
  27. using namespace std;
  28.  
  29. typedef long long vlong;
  30. typedef unsigned long long uvlong;
  31. typedef pair < int, int > pii;
  32. typedef pair < vlong, vlong > pll;
  33. typedef vector<pii> vii;
  34. typedef vector<int> vi;
  35.  
  36.  
  37. inline vlong gcd ( vlong a, vlong b ) {
  38. a = ABS ( a ); b = ABS ( b );
  39. while ( b ) { a = a % b; swap ( a, b ); } return a;
  40. }
  41.  
  42. /***********Template Ends Here***********/
  43. ///Custom Fraction Class
  44. class Fraction {
  45. vlong numerator, denominator;
  46.  
  47. void simplify() {
  48. vlong g = gcd ( numerator, denominator );
  49. numerator /= g;
  50. denominator /= g;
  51. if ( denominator < 0 ) {
  52. numerator *= -1;
  53. denominator *= -1;
  54. }
  55. }
  56.  
  57. public:
  58. Fraction () {
  59. numerator = 0;
  60. denominator = 1;
  61. }
  62. Fraction ( vlong a, vlong b ) {
  63. numerator = a;
  64. denominator = b;
  65. simplify();
  66. }
  67. Fraction ( vlong x ) {
  68. numerator = x;
  69. denominator = 1;
  70. }
  71. void operator = ( Fraction b ) {
  72. numerator = b.numerator;
  73. denominator = b.denominator;
  74. }
  75.  
  76. Fraction operator + ( Fraction b ) { ///Addition
  77. Fraction res;
  78. res.denominator = ABS( LCM(denominator,b.denominator) );
  79. res.numerator = (res.denominator/denominator)*numerator + (res.denominator/b.denominator)*b.numerator;
  80. res.simplify();
  81. return res;
  82. }
  83.  
  84. void print() {
  85. printf ( "%lld/%lld",numerator, denominator );
  86. }
  87. };
  88.  
  89. ///Calculate combinations
  90. vlong nck[25][25];
  91. void calcNCK(int n) {
  92. nck[0][0] = 1;
  93. FOR(i,1,n) {
  94. FOR(j,0,n) {
  95. if ( j == 0 ) nck[i][j] = 1;
  96. else nck[i][j] = nck[i-1][j-1] + nck[i-1][j];
  97. }
  98. }
  99. }
  100. void precal() {
  101. calcNCK(20);
  102. }
  103.  
  104. int menu[10010], item[10010];
  105.  
  106. ///DP to find expected value
  107. Fraction dp ( int pos ) {
  108. if ( pos < 0 ) return Fraction(0ll);
  109.  
  110. Fraction res;
  111.  
  112. vlong total = nck[ menu[pos] ][ item[pos] ];
  113. vlong chicken = nck[ menu[pos]-1 ][ item[pos]-1 ];
  114.  
  115. Fraction p ( chicken, total ), q ( total - chicken, total ); ///Calculate probabilities.
  116.  
  117. res = p + dp ( pos - 1 );
  118.  
  119. return res;
  120. }
  121.  
  122. int main () {
  123. precal();
  124. #ifdef forthright48
  125. freopen ( "input.txt", "r", stdin );
  126. //freopen ( "output.txt", "w", stdout );
  127. #endif // forthright48
  128.  
  129. int kase, cnt = 0;
  130. scanf ( "%d", &kase );
  131.  
  132. while ( kase-- ) {
  133. int m;
  134. scanf ( "%d", &m );
  135.  
  136. FOR(i,0,m-1) {
  137. scanf ( "%d %d", &menu[i], &item[i] );
  138. }
  139.  
  140. Fraction res = dp ( m - 1 );
  141.  
  142. printf ( "Case %d: ", ++cnt ); res.print(); nl;
  143. }
  144.  
  145. return 0;
  146. }
  147.  
Time limit exceeded #stdin #stdout 5s 3496KB
stdin
Standard input is empty
stdout
Standard output is empty