Appearance
question:def find_min_roads_to_remove(N: int, M: int, roads: List[Tuple[int, int]]) -> int: Determine the minimum number of roads to remove to make all intersections reachable from any other intersection. Args: N (int): The number of intersections. M (int): The number of roads. roads (List[Tuple[int, int]]): List of tuples where each tuple contains two integers representing a road between intersections. Returns: int: The minimum number of roads to remove. Examples: >>> find_min_roads_to_remove(5, 5, [(1, 2), (1, 3), (2, 3), (3, 4), (4, 5)]) 1 >>> find_min_roads_to_remove(4, 3, [(1, 2), (2, 3), (3, 4)]) 0 >>> find_min_roads_to_remove(4, 5, [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4)]) 2 >>> find_min_roads_to_remove(3, 3, [(1, 2), (2, 3), (1, 3)]) 1 >>> find_min_roads_to_remove(2, 1, [(1, 2)]) 0 >>> find_min_roads_to_remove(3, 0, []) 0 >>> find_min_roads_to_remove(3, 4, [(1, 1), (2, 2), (3, 3), (1, 2)]) 3
answer:def find_min_roads_to_remove(N, M, roads): def find_parent(parent, i): if parent[i] == i: return i return find_parent(parent, parent[i]) def union(parent, rank, x, y): root_x = find_parent(parent, x) root_y = find_parent(parent, y) if root_x != root_y: if rank[root_x] > rank[root_y]: parent[root_y] = root_x elif rank[root_x] < rank[root_y]: parent[root_x] = root_y else: parent[root_y] = root_x rank[root_x] += 1 parent = list(range(N)) rank = [0] * N removed_roads = 0 for u, v in roads: u -= 1 v -= 1 root_u = find_parent(parent, u) root_v = find_parent(parent, v) if root_u != root_v: union(parent, rank, root_u, root_v) else: removed_roads += 1 return removed_roads
question:def min_flips_to_no_adjacent_heads(n, coins): Given the number of coins and their initial states, return the minimum number of flips required so that no two adjacent coins show heads. >>> min_flips_to_no_adjacent_heads(5, 'TTTHT') 0 >>> min_flips_to_no_adjacent_heads(6, 'HHHHHH') 3 >>> min_flips_to_no_adjacent_heads(6, 'HTHTHT') 0 >>> min_flips_to_no_adjacent_heads(5, 'HHTTT') 1 >>> min_flips_to_no_adjacent_heads(5, 'TTTHH') 1 >>> min_flips_to_no_adjacent_heads(7, 'HHTHTHH') 2
answer:def min_flips_to_no_adjacent_heads(n, coins): Given the number of coins and their initial states, return the minimum number of flips required so that no two adjacent coins show heads. flips = 0 for i in range(1, n): if coins[i] == 'H' and coins[i - 1] == 'H': flips += 1 if i % 2 == 1: coins = coins[:i] + 'T' + coins[i + 1:] else: coins = coins[:i - 1] + 'T' + coins[i:] return flips
question:def count_people_seeing_front(N: int, heights: List[int]) -> int: Determine the number of people who can see the front of the queue. Parameters: N (int): Number of people in the queue. heights (list of int): Heights of the people in the queue. Returns: int: Number of people who can see the front. >>> count_people_seeing_front(5, [140, 150, 130, 160, 140]) 3 >>> count_people_seeing_front(5, [100, 100, 100, 100, 100]) 1 >>> count_people_seeing_front(5, [100, 120, 130, 140, 150]) 5 >>> count_people_seeing_front(5, [150, 140, 130, 120, 110]) 1 >>> count_people_seeing_front(6, [100, 180, 90, 190, 70, 200]) 4 >>> count_people_seeing_front(6, [10, 30, 20, 40, 30, 50]) 4
answer:def count_people_seeing_front(N, heights): Returns the number of people who can see the front of the queue. Parameters: N (int): Number of people in the queue. heights (list of int): Heights of the people in the queue. Returns: int: Number of people who can see the front. max_height = 0 count = 0 for height in heights: if height > max_height: max_height = height count += 1 return count
question:def max_happiness(n, l, happiness): Find the maximum possible happiness gain over any contiguous subarray of length L. Args: n (int): The number of attractions. l (int): The number of consecutive attractions the visitor plans to visit. happiness (List[int]): The happiness values of the attractions. Returns: int: The maximum possible happiness gain over any contiguous subarray of length L. Examples: >>> max_happiness(5, 3, [1, 2, 3, 4, 5]) 12 >>> max_happiness(6, 2, [-1, 2, 3, -1, 4, 5]) 9 pass def parse_input(input_str): Parse the input string into the required arguments. Args: input_str (str): Input string. Returns: Tuple[int, int, List[int]]: Parsed values of n, l, and the happiness array. Examples: >>> parse_input("5 3n1 2 3 4 5") (5, 3, [1, 2, 3, 4, 5]) >>> parse_input("6 2n-1 2 3 -1 4 5") (6, 2, [-1, 2, 3, -1, 4, 5]) pass def main(input_str): Main function to parse input, compute max happiness, and print the result. Args: input_str (str): Input string. Examples: >>> main("5 3n1 2 3 4 5") 12 >>> main("6 2n-1 2 3 -1 4 5") 9 pass # Unit Tests def test_max_happiness(): assert max_happiness(5, 3, [1, 2, 3, 4, 5]) == 12 assert max_happiness(6, 2, [-1, 2, 3, -1, 4, 5]) == 9 assert max_happiness(1, 1, [1000]) == 1000 assert max_happiness(3, 2, [-1, -2, -3]) == -3 assert max_happiness(6, 3, [1, 2, 1, 2, 1, 2]) == 5 def test_parse_input(): assert parse_input("5 3n1 2 3 4 5") == (5, 3, [1, 2, 3, 4, 5]) assert parse_input("6 2n-1 2 3 -1 4 5") == (6, 2, [-1, 2, 3, -1, 4, 5]) def test_main(capsys): main("5 3n1 2 3 4 5") captured = capsys.readouterr() assert captured.out.strip() == "12" main("6 2n-1 2 3 -1 4 5") captured = capsys.readouterr() assert captured.out.strip() == "9"
answer:def max_happiness(n, l, happiness): max_sum = current_sum = sum(happiness[:l]) for i in range(l, n): current_sum += happiness[i] - happiness[i - l] max_sum = max(max_sum, current_sum) return max_sum def parse_input(input_str): lines = input_str.strip().split('n') n, l = map(int, lines[0].split()) happiness = list(map(int, lines[1].split())) return n, l, happiness def main(input_str): n, l, happiness = parse_input(input_str) result = max_happiness(n, l, happiness) print(result)