# Vibe coded to make sure string-based solutions get AC. import sys def solve(): """ Solves the Draft Lottery problem by calculating the probability of every possible top-3 pick permutation and then aggregating these probabilities to find each team's final draft position odds. This version uses string keys for all probability data structures. """ # --- 1. Input Reading & Initialization --- try: N_str = sys.stdin.readline() if not N_str: return N = int(N_str) team_data = [] for _ in range(N): line = sys.stdin.readline().strip() parts = line.split() balls = int(parts[0]) name = parts[1] team_data.append({'balls': balls, 'name': name}) Q = int(sys.stdin.readline()) queries = [] for _ in range(Q): name, k_str = sys.stdin.readline().strip().split() queries.append((name, int(k_str))) except (IOError, ValueError): return # --- 2. Data Structuring --- # team_names are already sorted from worst to best record team_names = [data['name'] for data in team_data] balls_list = [data['balls'] for data in team_data] total_balls = sum(balls_list) # **MODIFICATION: Use dictionaries with string keys instead of lists of lists.** # The value is a list of size N+1 to allow for 1-based pick indexing. final_pick_probs = {name: [0.0] * (N + 1) for name in team_names} # --- 3. Main Probability Calculation --- # Handle edge cases for N < 3 if N == 1: if balls_list[0] > 0: final_pick_probs[team_names[0]][1] = 1.0 elif N == 2: if total_balls > 0: name0, name1 = team_names[0], team_names[1] balls0, balls1 = balls_list[0], balls_list[1] # Scenario 1: Team 0 gets pick 1, Team 1 gets pick 2 p_0_first = balls0 / total_balls final_pick_probs[name0][1] += p_0_first final_pick_probs[name1][2] += p_0_first # Scenario 2: Team 1 gets pick 1, Team 0 gets pick 2 p_1_first = balls1 / total_balls final_pick_probs[name1][1] += p_1_first final_pick_probs[name0][2] += p_1_first elif N >= 3: # This map stores the probability of each unique ordered triplet of teams # getting the first three picks. The key is a tuple of team names. prob_top3_map = {} # a. Calculate the probability for each top-3 permutation for i in range(N): p1 = balls_list[i] / total_balls denom2 = total_balls - balls_list[i] if denom2 <= 0: continue for j in range(N): if i == j: continue p2 = balls_list[j] / denom2 denom3 = total_balls - balls_list[i] - balls_list[j] if denom3 <= 0: continue for k in range(N): if k == i or k == j: continue p3 = balls_list[k] / denom3 key = (team_names[i], team_names[j], team_names[k]) prob_top3_map[key] = p1 * p2 * p3 # b. Use the map to determine the full draft order probability for each scenario for (p1_name, p2_name, p3_name), prob in prob_top3_map.items(): # Update probabilities for the top 3 lottery winners final_pick_probs[p1_name][1] += prob final_pick_probs[p2_name][2] += prob final_pick_probs[p3_name][3] += prob # For picks 4..N, find the remaining teams and assign picks # based on their original (worst-to-best) ranking. top3_names_set = {p1_name, p2_name, p3_name} current_pick = 4 # Iterate through teams in their original rank order for team_name in team_names: if team_name not in top3_names_set: final_pick_probs[team_name][current_pick] += prob current_pick += 1 # --- 4. Cumulative Probability Calculation --- # **MODIFICATION: This also becomes a dictionary.** cumulative_probs = {name: [0.0] * (N + 1) for name in team_names} for team_name in team_names: for k in range(1, N + 1): cumulative_probs[team_name][k] = cumulative_probs[team_name][k-1] + final_pick_probs[team_name][k] # --- 5. Answering Queries --- for team_name, k in queries: # Lookup is now direct, no index needed result = cumulative_probs[team_name][k] print(f"{result:.10f}") if __name__ == "__main__": solve()