// Sonny's solution to dice // Stanford Local Programming Contest, October 2007 #include #include using namespace std; const int digits = 5; const double sentry = -1.0; int dice[51]; double P[51][1001]; // recursive function to compute probability of roll of x double prob(int d, int x) { double p = 0.0, q = 1.0 / dice[d]; for (int i = 1; i <= dice[d]; ++i) if (x - i >= 0) p += q * ((P[d-1][x-i] == sentry) ? prob(d-1, x-i) : P[d-1][x-i]); P[d][x] = p; return p; } // program entry point int main() { int d; while (cin >> d) { if (d == 0) break; // read the dice char j; int n, maxroll = 0; for (int i = 1; i <= d; ++i) { cin >> j >> n; dice[i] = n; maxroll += n; } // read x, the target value int x; cin >> x; // check trivial case if (x < d || x > maxroll) cout << fixed << setprecision(digits) << 0.0 << endl; else { // clear memoization table for (int i = 0; i <= d; ++i) for (int j = 0; j <= maxroll; ++j) P[i][j] = i ? sentry : 0.0; P[0][0] = 1.0; cout << fixed << setprecision(digits) << prob(d, x) << endl; } } return 0; }