// Simulates the draft lottery a bunch of times. // Update NUM_OPERATIONS to make it faster/slower once a time limit is known. #include using namespace std; // Sorry for hard-coding. :( const int MAX_TEAMS = 50; const int MAX_BALLS = 50; // per team const int NUM_OPERATIONS = 30000000; struct Team { string name; int balls; int order; }; int odds[MAX_TEAMS + 1][MAX_TEAMS + 1]; int balls[(MAX_TEAMS + 1) * (MAX_BALLS + 1)]; int num_balls; std::minstd_rand rng; int drawn[3]; bool is_drawn[MAX_TEAMS]; int place[MAX_TEAMS]; void simulate_one(int num_teams) { memset(is_drawn, 0, sizeof(is_drawn)); std::uniform_int_distribution dist(0, num_balls - 1); int draws = min(3, num_teams); for (int i = 0; i < draws; i++) { while (true) { int ball = balls[dist(rng)]; if (is_drawn[ball]) continue; drawn[i] = ball; is_drawn[ball] = true; break; } } for (int i = 0; i < draws; i++) odds[drawn[i]][i]++; for (int i = 0; i < num_teams; i++) place[i] = i; for (int k = 0; k < draws; k++) { for (int i = 0; i < drawn[k]; i++) place[i]++; } for (int i = 0; i < num_teams; i++) { if (!is_drawn[i]) odds[i][place[i]]++; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector teams(n); int idx = 0; for (auto &[name, balls, order] : teams) { cin >> balls >> name; order = idx++; } num_balls = 0; for (int i = 0; i < n; i++) for (int j = 0; j < teams[i].balls; j++) balls[num_balls++] = i; int num_simulations = NUM_OPERATIONS / n; for (int i = 0; i < num_simulations; i++) simulate_one(n); int Q; cin >> Q; while (Q--) { string team; int place; cin >> team >> place; int team_idx = 0; while (teams[team_idx].name != team) team_idx++; int tot = 0; for (int p = 0; p < place; p++) tot += odds[teams[team_idx].order][p]; cout << fixed << setprecision(10) << tot / 1.0 / num_simulations << '\n'; } }