fork(2) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mGKwuL
Blog
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!