Appearance
question:def findWinner(M, N, grid): Determines the winner of the game where Alice and Bob collect crystals optimally. Parameters: M (int): The number of rows in the grid. N (int): The number of columns in the grid. grid (List[List[str]]): The grid representing the forest path, with 'C' indicating a crystal and '.' an empty cell. Returns: str: The winner of the game, either "ALICE", "BOB", or "DRAW". Example: >>> findWinner(3, 3, [['C', '.', 'C'], ['.', 'C', '.'], ['C', '.', 'C']]) 'ALICE' >>> findWinner(2, 2, [['.', 'C'], ['C', '.']]) 'DRAW' from solution import findWinner def test_find_winner_example1(): M = 3 N = 3 grid = [ ['C', '.', 'C'], ['.', 'C', '.'], ['C', '.', 'C'] ] assert findWinner(M, N, grid) == "ALICE" def test_find_winner_example2(): M = 2 N = 2 grid = [ ['.', 'C'], ['C', '.'] ] assert findWinner(M, N, grid) == "DRAW" def test_find_winner_no_crystals(): M = 3 N = 3 grid = [ ['.', '.', '.'], ['.', '.', '.'], ['.', '.', '.'] ] assert findWinner(M, N, grid) == "DRAW" def test_find_winner_crystals_unequal_distribution(): M = 3 N = 3 grid = [ ['C', 'C', '.'], ['C', 'C', '.'], ['.', '.', '.'] ] assert findWinner(M, N, grid) == "ALICE" def test_find_winner_all_crystals(): M = 2 N = 2 grid = [ ['C', 'C'], ['C', 'C'] ] assert findWinner(M, N, grid) == "ALICE"
answer:def findWinner(M, N, grid): # Possible move directions for a player (up, down, left, right) directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] def valid_move(x, y, visited): return 0 <= x < M and 0 <= y < N and not visited[x][y] and grid[x][y] != '#' def bfs(start): queue = [start] visited = [[False] * N for _ in range(M)] visited[start[0]][start[1]] = True crystals = 1 if grid[start[0]][start[1]] == 'C' else 0 while queue: x, y = queue.pop(0) for d in directions: nx, ny = x + d[0], y + d[1] if valid_move(nx, ny, visited): visited[nx][ny] = True queue.append((nx, ny)) if grid[nx][ny] == 'C': crystals += 1 return crystals alice_crystals = bfs((0, 0)) bob_crystals = 0 for x in range(M): for y in range(N): if (x, y) != (0, 0) and grid[x][y] == 'C': bob_crystals += 1 if alice_crystals > bob_crystals: return "ALICE" elif bob_crystals > alice_crystals: return "BOB" else: return "DRAW"
question:def max_consecutive_successful_weeks(m: int, w: int, weeks: List[str]) -> int: This function returns the maximum number of consecutive successful weeks. >>> max_consecutive_successful_weeks(3, 3, ["AAN", "NAA", "AAN"]) == 3 >>> max_consecutive_successful_weeks(2, 4, ["NA", "AN", "NN", "AA"]) == 2 >>> max_consecutive_successful_weeks(2, 3, ["NN", "AN", "NN"]) == 1 >>> max_consecutive_successful_weeks(1, 1, ["N"]) == 0 >>> max_consecutive_successful_weeks(4, 4, ["AAAA", "AANA", "NNNN", "ANNA"]) == 2 >>> max_consecutive_successful_weeks(5, 5, ["NNNNN", "NNNNA", "NNNNN", "ANNNN", "NNNNN"]) == 1 >>> max_consecutive_successful_weeks(4, 4, ["NNNN", "NNNN", "NNNN", "NNNN"]) == 0 >>> max_consecutive_successful_weeks(3, 5, ["AAA", "AAA", "NNN", "AAA", "NNA"]) == 2 >>> max_consecutive_successful_weeks(2, 6, ["NA", "AN", "NA", "NN", "AN", "NA"]) == 3
answer:def max_consecutive_successful_weeks(m, w, weeks): This function returns the maximum number of consecutive successful weeks. Parameters: m (int): number of team members w (int): number of weeks weeks (List[str]): list of strings representing attendance patterns max_streak = 0 current_streak = 0 for week in weeks: if 'A' in week: current_streak += 1 max_streak = max(max_streak, current_streak) else: current_streak = 0 return max_streak
question:class SegmentTree: def __init__(self, data): self.n = len(data) self.tree = [0] * (2 * self.n) self.build(data) def build(self, data): for i in range(self.n): self.tree[self.n + i] = data[i] for i in range(self.n - 1, 0, -1): self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1] def update(self, pos, value): pos += self.n self.tree[pos] = value while pos > 1: pos //= 2 self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1] def range_sum(self, l, r): l += self.n r += self.n + 1 sum = 0 while l < r: if l % 2 == 1: sum += self.tree[l] l += 1 if r % 2 == 1: r -= 1 sum += self.tree[r] l //= 2 r //= 2 return sum def handle_operations(N, A, M, operations): Handle a series of update operations and range sum queries on an array. Args: N: int - The size of the array. A: List[int] - The array of integers. M: int - The number of operations to be performed. operations: List[Tuple[int, int, int]] - A list of operations, where each operation is either: (1, x, y) - an update operation to change the value at index x to y. (2, l, r) - a range sum query to compute the sum of elements from index l to r. Returns: List[int] - The results of the range sum queries. Example: >>> handle_operations(5, [1, 2, 3, 4, 5], 3, [(2, 1, 3), (1, 2, 10), (2, 1, 3)]) [6, 14]
answer:class SegmentTree: def __init__(self, data): self.n = len(data) self.tree = [0] * (2 * self.n) self.build(data) def build(self, data): for i in range(self.n): self.tree[self.n + i] = data[i] for i in range(self.n - 1, 0, -1): self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1] def update(self, pos, value): pos += self.n self.tree[pos] = value while pos > 1: pos //= 2 self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1] def range_sum(self, l, r): l += self.n r += self.n + 1 sum = 0 while l < r: if l % 2 == 1: sum += self.tree[l] l += 1 if r % 2 == 1: r -= 1 sum += self.tree[r] l //= 2 r //= 2 return sum def handle_operations(N, A, M, operations): seg_tree = SegmentTree(A) results = [] for op in operations: if op[0] == 1: seg_tree.update(op[1] - 1, op[2]) elif op[0] == 2: results.append(seg_tree.range_sum(op[1] - 1, op[2] - 1)) return results
question:from typing import List, Tuple class SegmentTree: def __init__(self, array: List[int]): self.n = len(array) self.tree = [0] * (2 * self.n) self.build(array) def build(self, array: List[int]): # Initialize the leaves of the tree for i in range(self.n): self.tree[self.n + i] = array[i] # Initialize the internal nodes for i in range(self.n - 1, 0, -1): self.tree[i] = max(self.tree[2 * i], self.tree[2 * i + 1]) def update(self, pos: int, value: int): pos += self.n self.tree[pos] = value while pos > 1: pos //= 2 self.tree[pos] = max(self.tree[2 * pos], self.tree[2 * pos + 1]) def range_max(self, left: int, right: int) -> int: left += self.n right += self.n maximum = -1 while left < right: if left % 2: maximum = max(maximum, self.tree[left]) left += 1 if right % 2: right -= 1 maximum = max(maximum, self.tree[right]) left //= 2 right //= 2 return maximum def process_queries(N: int, Q: int, array: List[int], queries: List[Tuple[int, int, int]]) -> List[int]: Process segment tree queries for updates and range maximum. Args: N (int): The number of elements in the array. Q (int): The number of queries. array (List[int]): The initial elements of the array. queries (List[Tuple[int, int, int]]): The queries to process. Returns: List[int]: The results of the range maximum queries. >>> array = [1, 5, 2, 4, 3] >>> queries = [ (2, 1, 3), (1, 4, 10), (2, 2, 5), (1, 1, 20), (2, 3, 3) ] >>> process_queries(5, 5, array, queries) [5, 10, 2] >>> array = [2] >>> queries = [ (1, 1, 3), (2, 1, 1) ] >>> process_queries(1, 2, array, queries) [3] seg_tree = SegmentTree(array) results = [] for query in queries: if query[0] == 1: _, x, y = query seg_tree.update(x - 1, y) elif query[0] == 2: _, x, y = query results.append(seg_tree.range_max(x - 1, y)) return results
answer:class SegmentTree: def __init__(self, array): self.n = len(array) self.tree = [0] * (2 * self.n) self.build(array) def build(self, array): # Initialize the leaves of the tree for i in range(self.n): self.tree[self.n + i] = array[i] # Initialize the internal nodes for i in range(self.n - 1, 0, -1): self.tree[i] = max(self.tree[2 * i], self.tree[2 * i + 1]) def update(self, pos, value): pos += self.n self.tree[pos] = value while pos > 1: pos //= 2 self.tree[pos] = max(self.tree[2 * pos], self.tree[2 * pos + 1]) def range_max(self, left, right): left += self.n right += self.n maximum = -1 while left < right: if left % 2: maximum = max(maximum, self.tree[left]) left += 1 if right % 2: right -= 1 maximum = max(maximum, self.tree[right]) left //= 2 right //= 2 return maximum def process_queries(N, Q, array, queries): seg_tree = SegmentTree(array) results = [] for query in queries: if query[0] == 1: _, x, y = query seg_tree.update(x - 1, y) elif query[0] == 2: _, x, y = query results.append(seg_tree.range_max(x - 1, y)) return results