Appearance
question:def propagate_magic(n, m, connections, queries): Determine if there's a pair of distinct cities such that the maximum magic factor on the path between them is exactly equal to the given magic factor. >>> propagate_magic(5, 6, [(1, 2, 10), (2, 3, 15), (3, 4, 20), (4, 5, 25), (1, 3, 30), (2, 5, 35)], [10, 20, 1]) ["YES", "YES", "NO"] >>> propagate_magic(4, 3, [(1, 2, 5), (2, 3, 10), (3, 4, 5)], [5, 10, 20]) ["YES", "YES", "NO"] def main(inputs): Parse input for the propagate_magic function and return the results for the queries. >>> main("5 6 3n1 2 10n2 3 15n3 4 20n4 5 25n1 3 30n2 5 35n10n20n1n") ["YES", "YES", "NO"] >>> main("4 3 3n1 2 5n2 3 10n3 4 5n5n10n20n") ["YES", "YES", "NO"]
answer:def propagate_magic(n, m, connections, queries): from collections import defaultdict # Graph data structure graph = defaultdict(list) # Insert each road into the graph for u, v, c in connections: graph[c].append((u, v)) # Use a set to store all magic factors in the connections magic_factors = set(graph.keys()) # Prepare the results for each query results = [] for query in queries: if query in magic_factors: results.append("YES") else: results.append("NO") return results def main(inputs): lines = inputs.strip().split('n') n, m, q = map(int, lines[0].split()) index = 1 connections = [] for _ in range(m): u, v, c = map(int, lines[index].split()) connections.append((u, v, c)) index += 1 queries = [] for _ in range(q): k = int(lines[index]) queries.append(k) index += 1 return propagate_magic(n, m, connections, queries)
question:def marathon_medals(n: int, finishing_times: List[int]) -> Tuple[int, int, int, int]: Determines the number of participants receiving gold, silver, and bronze medals, and those who do not receive any medals. Parameters: n (int): Number of participants. finishing_times (list): A list of unique positive integers representing the finishing times. Returns: tuple: A tuple containing four integers: the number of gold medalists, silver medalists, bronze medalists, and non-medalists. Examples: >>> marathon_medals(9, [2, 1, 3, 5, 4, 6, 8, 7, 9]) (3, 3, 3, 0) >>> marathon_medals(5, [10, 5, 3, 8, 7]) (1, 1, 1, 2)
answer:def marathon_medals(n, finishing_times): Determines the number of participants receiving gold, silver, and bronze medals, and those who do not receive any medals. Parameters: n (int): Number of participants. finishing_times (list): A list of unique positive integers representing the finishing times. Returns: tuple: A tuple containing four integers: the number of gold medalists, silver medalists, bronze medalists, and non-medalists. # Calculate the number of people in each medal category medals_per_category = n // 3 # Calculate the number of participants who will not receive any medals no_medals = n % 3 # Number of gold, silver, and bronze medals will all be equal gold = silver = bronze = medals_per_category return (gold, silver, bronze, no_medals)
question:def can_assign_activities(n: int, m: int, capacities: List[int], preferences: List[List[int]]) -> str: Determine if it's possible to assign all guests to one of their preferred activities while respecting the capacities. Args: n (int): the number of guests. m (int): the number of activities. capacities (List[int]): a list of capacities for each activity. preferences (List[List[int]]): a list of lists, where each sublist contains the activities a guest is interested in. Returns: str: "YES" if all guests can be assigned without violating activity capacities, otherwise "NO". Example: >>> can_assign_activities(5, 3, [2, 2, 2], [[1, 2], [1, 3], [3], [1], [2, 3]]) "YES" >>> can_assign_activities(4, 2, [1, 1], [[1], [1], [1], [1]]) "NO" pass # Your code here # Testing def test_example_case(): n = 5 m = 3 capacities = [2, 2, 2] preferences = [ [1, 2], [1, 3], [3], [1], [2, 3] ] assert can_assign_activities(n, m, capacities, preferences) == "YES" def test_more_activities_than_needed(): n = 3 m = 5 capacities = [1, 1, 1, 1, 1] preferences = [ [1, 2], [2, 3], [1, 4] ] assert can_assign_activities(n, m, capacities, preferences) == "YES" def test_no_possible_assignment(): n = 4 m = 2 capacities = [1, 1] preferences = [ [1], [1], [1], [1] ] assert can_assign_activities(n, m, capacities, preferences) == "NO" def test_all_guests_have_one_pref_each(): n = 3 m = 3 capacities = [1, 1, 1] preferences = [ [1], [2], [3] ] assert can_assign_activities(n, m, capacities, preferences) == "YES" def test_exact_fit_case(): n = 3 m = 3 capacities = [1, 1, 1] preferences = [ [1, 2], [2, 3], [1, 3] ] assert can_assign_activities(n, m, capacities, preferences) == "YES"
answer:def can_assign_activities(n, m, capacities, preferences): # Initialize the usage of each activity to 0 usage = [0] * m # Create a list of guests' preferences with their index guests = [] for i, prefs in enumerate(preferences): guests.append((len(prefs), prefs)) # Sort guests by the number of their preferences (least preferred first) guests.sort() # Try to assign each guest to one of their preferred activities for _, prefs in guests: assigned = False for activity in prefs: if usage[activity - 1] < capacities[activity - 1]: # 1-based to 0-based index usage[activity - 1] += 1 assigned = True break if not assigned: return "NO" return "YES"
question:def min_removals_to_make_palindrome(s: str) -> int: Determine the minimum number of characters Lina needs to remove to make the string `s` a palindrome. >>> min_removals_to_make_palindrome("abcde") 4 >>> min_removals_to_make_palindrome("abacaba") 0
answer:def min_removals_to_make_palindrome(s): Returns the minimum number of characters to remove to make the string a palindrome. n = len(s) # Creating a reverse of the string rev_s = s[::-1] # Initialize a table to store lengths of longest common subsequences. dp = [[0] * (n + 1) for _ in range(n + 1)] # Fill dp table for i in range(n + 1): for j in range(n + 1): if i == 0 or j == 0: dp[i][j] = 0 elif s[i - 1] == rev_s[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # The length of longest palindromic subsequence lps = dp[n][n] # Minimum number of deletions to make the string a palindrome return n - lps