Appearance
question:def longest_almost_geometric_subsequence(n: int, sequence: List[int]) -> int: Gina has recently taken an interest in "almost geometric progressions". A sequence is considered an almost geometric progression if its elements can be represented as: a[i] = a[1] * q^(i-1) + d where `q` is a constant ratio, `d` is a constant difference, and `i` indicates the element's position in the sequence. Given a sequence of integers, Gina wants to find the longest subsequence that is an almost geometric progression. A subsequence is derived by removing zero or more elements from the original sequence without changing the order of the remaining elements. Parameters: - n: int, representing the number of elements in the sequence - sequence: List[int], the elements of the sequence Returns: - int, representing the length of the longest subsequence that is an almost geometric progression. >>> longest_almost_geometric_subsequence(5, [2, 4, 8, 16, 32]) 5 >>> longest_almost_geometric_subsequence(6, [1, 2, 4, 8, 7, 64]) 4 >>> longest_almost_geometric_subsequence(1, [1]) 1 >>> longest_almost_geometric_subsequence(2, [1, 3]) 2 >>> longest_almost_geometric_subsequence(5, [1, 10, 20, 30, 40]) 2
answer:def longest_almost_geometric_subsequence(n, sequence): def is_almost_geometric(subseq): if len(subseq) < 2: return True q = subseq[1] / subseq[0] d = subseq[1] - q * subseq[0] for i, val in enumerate(subseq): if not (val == subseq[0] * (q ** i) + d): return False return True max_length = 0 for i in range(n): for j in range(i + 1, n + 1): subseq = sequence[i:j] if is_almost_geometric(subseq): max_length = max(max_length, len(subseq)) return max_length # Sample Usage: # n = 5 # sequence = [2, 4, 8, 16, 32] # print(longest_almost_geometric_subsequence(n, sequence)) # Output: 5
question:from typing import List, Tuple def monitor_access_events(n: int, m: int, events: List[Tuple[int, ...]]) -> List[int]: A network administrator needs to monitor server activity across multiple data centers. You need to write a program to help the administrator aggregate these logs to determine how many unique users have accessed any servers during the monitoring period. >>> monitor_access_events(3, 5, [(1, 1001, 1), (1, 1002, 2), (2, 3), (1, 1001, 3), (2, 5)]) [2, 2] >>> monitor_access_events(1, 3, [(1, 1001, 1), (2, 2), (2, 3)]) [1, 1] >>> monitor_access_events(5, 6, [(1, 1001, 1), (1, 1002, 2), (1, 1003, 3), (1, 1004, 4), (2, 5), (1, 1002, 5)]) [4] >>> monitor_access_events(2, 4, [(1, 101, 1), (1, 102, 1), (1, 103, 2), (2, 3)]) [3] >>> monitor_access_events(5, 3, [(2, 1), (2, 2), (2, 3)]) [0, 0, 0]
answer:def monitor_access_events(n, m, events): from collections import defaultdict # Dictionary to keep track of unique users on each server servers = defaultdict(set) # List to gather results of queries results = [] # Set to keep track of unique users globally unique_users = set() for i in range(m): event = events[i] if event[0] == 1: # Access event _, user, server = event if user not in servers[server]: servers[server].add(user) unique_users.add(user) elif event[0] == 2: # Query event _, time = event results.append(len(unique_users)) return results # Example input output n = 3 m = 5 events = [ (1, 1001, 1), (1, 1002, 2), (2, 3), (1, 1001, 3), (2, 5) ] print(monitor_access_events(n, m, events)) # Expected Output: [2, 2]
question:def max_sum_subarray_of_length_k(n: int, k: int, A: List[int]) -> int: Computes the maximum possible sum of a subarray of length exactly k, modulo 10^9 + 7. Args: n (int): The number of elements in the array. k (int): The length of the subarray. A (list of int): The array of integers. Returns: int: The maximum possible sum modulo 10^9 + 7. Example: >>> max_sum_subarray_of_length_k(5, 3, [1, 2, 3, 4, 5]) 12 >>> max_sum_subarray_of_length_k(1, 1, [1000000000]) 1000000000 % (10**9 + 7) >>> max_sum_subarray_of_length_k(5, 2, [-1, -2, -3, -4, -5]) (-1 - 2) % (10**9 + 7) >>> max_sum_subarray_of_length_k(5, 5, [1, 2, -3, 4, 5]) 9 >>> max_sum_subarray_of_length_k(1000000, 1, [i for i in range(1, 1000001)]) 1000000 % (10**9 + 7)
answer:def max_sum_subarray_of_length_k(n, k, A): Computes the maximum possible sum of a subarray of length exactly k, modulo 10^9 + 7. Args: n (int): The number of elements in the array. k (int): The length of the subarray. A (list of int): The array of integers. Returns: int: The maximum possible sum modulo 10^9 + 7. MOD = 10**9 + 7 current_sum = sum(A[:k]) max_sum = current_sum for i in range(n - k): current_sum = current_sum - A[i] + A[i + k] max_sum = max(max_sum, current_sum) return max_sum % MOD
question:def max_visited_cells(n: int, m: int) -> int: Returns the maximum number of cells that can be visited on an n x m grid if Saitama and Genos play optimally. >>> max_visited_cells(3, 3) 9 >>> max_visited_cells(1, 1) 1 >>> max_visited_cells(2, 2) 4 >>> max_visited_cells(4, 7) 28 >>> max_visited_cells(1000, 1000) 1000000
answer:def max_visited_cells(n, m): Returns the maximum number of cells that can be visited on an n x m grid if Saitama and Genos play optimally. # Since both players play optimally to visit the maximum number of cells # The answer is straightforward as they will always be able to visit all cells return n * m