1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
  #include <stdio.h>
  #include <cstdio>
  #include <string>
  using namespace std;

  long long commonDivisor(long long x, long long y) {
    return x == 0 ? y :
           y == 0 ? x :
           x > y  ? commonDivisor(x % y, y) :
             commonDivisor(y % x, x);
  }

  long long commonMultiple(long long x, long long y) {
    return x / commonDivisor(x, y) * y;
  }

  struct Ratio {
    long long num;
    long long den;
  };

  Ratio normalize(Ratio ratio) {
    long long divisor = commonDivisor(ratio.num, ratio.den);
    return { ratio.num / divisor, ratio.den / divisor };
  }

  Ratio add(Ratio a, Ratio b) {
    long long den = commonMultiple(a.den, b.den);
    long long num = den / a.den * a.num + den / b.den * b.num;
    return normalize({ num, den });
  }

  Ratio divide(Ratio ratio, long long divisor) {
    return normalize( { ratio.num, ratio.den * divisor } );
  }

  const int MAX_N = 100;

  int main() {
    int nPlatforms;
    cin >> nPlatforms;

    // initialize platforms charge
    Ratio currentAtPlatform[MAX_N];
    currentAtPlatform[0] = { 1, 1 };
    for (int iPlatform = 1; iPlatform < nPlatforms; iPlatform++) {
      currentAtPlatform[iPlatform] = { 0, 1 };
    }

    long long uberDenominator = 1;
    for (int iPlatform = 0; iPlatform < nPlatforms; iPlatform++) {
      Ratio current = currentAtPlatform[iPlatform];
      int nExits;
      cin >> nExits;

      if (nExits > 0) {
        Ratio currentPerExit = divide(current, nExits);
        uberDenominator = commonMultiple(uberDenominator, currentPerExit.den);
        for (int i = 0; i < nExits; i++) {
          int idPlatform;
          cin >> idPlatform;
          idPlatform--;
          currentAtPlatform[idPlatform] = add(currentAtPlatform[idPlatform], currentPerExit);
        }
      }
    }

    printf("%lld\n", uberDenominator);
    return 0;
  }