Appearance
question:You are given a list of words and a list of queries. Each query consists of one character, and for each query, you have to find the first word in the list that starts with the given character. If no such word exists, return "Not found". Write a function that processes the list of words and the queries effectively. Input: - The first line contains two integers n and q (1 ≤ n, q ≤ 10^5), the number of words and the number of queries respectively. - The next n lines contain one word each. - The next q lines contain one character each (a single lowercase Latin letter). Output: - For each query, print the first word that starts with the given character or "Not found" if no such word exists. Example: Input: 5 3 apple banana apricot grape avocado a b c Output: apple banana Not found
answer:def process_queries(words, queries): Processes words list and queries list to find the first word that starts with the query character. Args: words -- list of words queries -- list of single character queries Returns: List of results for each query result = [] word_dict = {} # Populate the dictionary with the first occurrence of each starting letter for word in words: first_letter = word[0] if first_letter not in word_dict: word_dict[first_letter] = word # Find and prepare the results for each query for query in queries: result.append(word_dict.get(query, "Not found")) return result
question:A library system maintains records of books and their circulation statuses. Each book is represented by an integer ID and has a record of when it was borrowed and returned. The system tracks the books in the form of a list of events, where each event can either be a borrowing event or a returning event. Your task is to write a program that determines the maximum number of books that were borrowed from the library at any single point in time. The first line of input contains an integer n (1 ≤ n ≤ 1000) — the number of events. Each of the next n lines describes an event. Each event is composed of an integer t (1 ≤ t ≤ 10^6) representing the timestamp of the event, followed by a character type that can be either 'B' (borrow) or 'R' (return), and an integer ID (1 ≤ ID ≤ 10^9) representing the ID of the book. Output a single integer — the maximum number of books that were borrowed at the same time. # Example Input ``` 5 1 B 101 2 B 102 3 R 101 4 B 103 5 R 102 ``` Output ``` 2 ``` Explanation At timestamp 2 and 4, two books are borrowed at the same time.
answer:def max_books_borrowed_at_once(n, events): Determines the maximum number of books borrowed from the library at a single point in time. :param n: Integer, number of events :param events: List of tuples, each containing a timestamp, a character ('B' or 'R'), and an integer book ID :return: Integer, the maximum number of books borrowed at the same time borrowed_books = set() max_borrowed = 0 for time, event, book_id in events: if event == 'B': borrowed_books.add(book_id) elif event == 'R': borrowed_books.discard(book_id) max_borrowed = max(max_borrowed, len(borrowed_books)) return max_borrowed
question:The robotics team at a tech university is facing a problem with the delivery of supplies using drones. The campus can be represented as a grid of size `n x m`, where some cells contain obstacles and others are open spaces. Each drone can move up, down, left, or right, but cannot move diagonally. The drones need to deliver supplies to specific target cells from a starting cell. The team wants to find the shortest path for each delivery without hitting any obstacles. Each test case consists of the grid size `n` and `m`, the grid representation with obstacles and open spaces, the start cell `(sx, sy)`, and the target cell `(tx, ty)`. An obstacle is denoted by `'#'`, and an open space is denoted by `'.'`. You need to determine the shortest number of moves required for the drone to reach the target cell from the start cell. If it is not possible to reach the target cell, output `-1`. The input format is: - The first line contains an integer `t`, the number of test cases. - For each test case: - The first line contains two integers `n` and `m` (1 <= n, m <= 1000), the size of the grid. - Each of the next `n` lines contains a string of length `m` representing the grid. - The next line contains four integers `sx`, `sy`, `tx`, `ty` (0 <= sx, sy, tx, ty < n, m), representing the start and target cell coordinates. The output format is: - For each test case, output a single integer representing the shortest number of moves required for the drone to reach the target cell, or `-1` if it is impossible. Example input: ``` 2 4 4 .... .#.. .... .... 0 0 3 3 3 0 0 3 4 4 #. #..# 0 0 2 2 0 1 2 2 ``` Example output: ``` 6 -1 ``` Explain the example: - In the first test case, the drone can move from (0, 0) to (3, 3) in 6 moves. - In the second test case, it is impossible to reach the target cell from the start cell.
answer:from collections import deque def shortest_path(grid, start, target): Returns the shortest path from start to target in a grid, avoiding obstacles. If no path is found, returns -1. Parameters: grid (list of list of str): Grid representation with '.' for open spaces and '#' for obstacles. start (tuple of int): The (x, y) starting coordinate. target (tuple of int): The (x, y) target coordinate. Returns: int: The shortest number of moves required, or -1 if the target is unreachable. n, m = len(grid), len(grid[0]) sx, sy = start tx, ty = target if grid[sx][sy] == '#' or grid[tx][ty] == '#': return -1 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] visited = [[False for _ in range(m)] for _ in range(n)] queue = deque([(sx, sy, 0)]) # (current_x, current_y, current_distance) visited[sx][sy] = True while queue: x, y, dist = queue.popleft() if (x, y) == (tx, ty): return dist for dx, dy in directions: nx, ny = x + dx, y + dy if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and grid[nx][ny] == '.': visited[nx][ny] = True queue.append((nx, ny, dist + 1)) return -1 def process_test_cases(t, test_cases): Handles multiple test cases for the shortest path calculation. Parameters: t (int): Number of test cases. test_cases (list of tuples): Each tuple contains (n, m, grid, start, target). Returns: list: The results of the shortest path calculation for each test case. results = [] for case in test_cases: n, m, grid, (sx, sy), (tx, ty) = case result = shortest_path(grid, (sx, sy), (tx, ty)) results.append(result) return results # Example usage if __name__ == "__main__": t = 2 test_cases = [ (4, 4, ["....", ".#..", "....", "...."], (0, 0), (3, 3)), (4, 4, ["", "#.", "#..#", ""], (0, 0), (2, 2)) ] results = process_test_cases(t, test_cases) for res in results: print(res)
question:Alina likes creating new sequences. Recently, she became interested in sequences of integers that match a set of specific rules. Alina defines a "balanced sequence" as a sequence that fulfills the following conditions: 1. The length of the sequence is even, denoted by (2n). 2. The sequence contains exactly (n) numbers equal to 1 and (n) numbers equal to -1. 3. Any prefix of the sequence has a sum that is greater than or equal to zero. For example, the sequences [1, -1, 1, -1], [1, 1, -1, -1], and [1, 1, 1, -1, -1, -1] are balanced, but the sequences [1, -1, -1, 1], [-1, 1, 1, -1], and [1, -1, 1] are not. Alina's challenge for you is to determine whether a given sequence is a balanced sequence. The first line of the input contains an integer (t) (1 ≤ (t) ≤ 100) — the number of test cases. Each test case consists of two lines. The first line of each test case contains an even integer (2n) (2 ≤ (2n) ≤ 50) — the length of the sequence. The second line contains (2n) integers (a_1, a_2, ..., a_{2n}) denoting the sequence (each integer in the sequence is either 1 or -1). For each test case, print "YES" if the given sequence is balanced, and "NO" otherwise. # Example Input ``` 3 4 1 -1 1 -1 4 1 -1 -1 1 6 1 1 1 -1 -1 -1 ``` Output ``` YES NO YES ``` # Note - In the first test case, [1, -1, 1, -1] is a balanced sequence, as any prefix of the sequence does not have a negative sum. - In the second test case, [1, -1, -1, 1] is not a balanced sequence because the prefix [1, -1, -1] has a sum of -1. - In the third test case, [1, 1, 1, -1, -1, -1] is a balanced sequence.
answer:def is_balanced_sequence(t, test_cases): results = [] for case in test_cases: length = case[0] sequence = case[1] # Check if the counts of 1s and -1s are equal if sequence.count(1) != length // 2 or sequence.count(-1) != length // 2: results.append("NO") continue # Check if every prefix sum is non-negative prefix_sum = 0 balanced = True for num in sequence: prefix_sum += num if prefix_sum < 0: balanced = False break if balanced: results.append("YES") else: results.append("NO") return results