Appearance
question:Determine if a given set of points form a convex polygon. You will be given a list of points in 2D plane and you need to determine if these points form a convex polygon or not. A polygon is convex if all its internal angles are less than 180 degrees. Constraints * 3 ≤ n ≤ 100 * -1000 ≤ xi, yi ≤ 1000 Input The input consists of the number of test cases t, followed by t test cases. Each test case starts with n, the number of points, followed by n pairs of integers xi and yi representing the coordinates of the points. Output For each test case, output "YES" if the points form a convex polygon and "NO" otherwise. Example Input 2 4 0 0 0 1 1 1 1 0 5 0 0 2 2 4 0 3 3 1 3 Output YES NO
answer:def is_convex_polygon(points): def cross_product(p1, p2, p3): return (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0]) n = len(points) if n < 3: return False last_product_sign = 0 for i in range(n): p1 = points[i] p2 = points[(i + 1) % n] p3 = points[(i + 2) % n] cross_prod = cross_product(p1, p2, p3) current_sign = (cross_prod > 0) - (cross_prod < 0) if current_sign != 0: if last_product_sign == 0: last_product_sign = current_sign elif last_product_sign != current_sign: return False return True def check_convex_polygons(test_cases): result = [] for points in test_cases: if is_convex_polygon(points): result.append("YES") else: result.append("NO") return result # Parsing input def parse_input(input_str): lines = input_str.strip().split() index = 0 t = int(lines[index]) index += 1 test_cases = [] for _ in range(t): n = int(lines[index]) index += 1 points = [] for _ in range(n): x, y = int(lines[index]), int(lines[index+1]) points.append((x, y)) index += 2 test_cases.append(points) return test_cases def solution(input_str): test_cases = parse_input(input_str) result = check_convex_polygons(test_cases) return 'n'.join(result) # Example usage input_str = '2n4 0 0 0 1 1 1 1 0n5 0 0 2 2 4 0 3 3 1 3' print(solution(input_str))
question:A grocery store has multiple aisles, each containing a set of shelves. Each shelf has its own set of products, and customers often rearrange items while shopping, leading to misplaced products. Your task is to determine if the products can be rearranged such that: 1. Each shelf in an aisle contains the same type of product. 2. No product type is found in more than one shelf in a single aisle. Example aisles = [[1, 2, 0], [0, 1, 2]] The store has n=2 aisles and m=3 shelves in each aisle. The distribution of product types per shelf is shown in the following diagram: In this case, a possible rearrangement would be: * For the first aisle: Move the product of type 2 to shelf 0 and product of type 1 to shelf 2, so that shelves 0,1,2 will have products 2,0,1 respectively. The diagram below shows the possible rearrangement: Thus, it is possible to arrange each aisle such that each shelf contains only one type of product, and no product type is found in more than one shelf within an aisle. Function Description Complete the `organizeAisles` function in the editor below. `organizeAisles` has the following parameter(s): - `int aisles[n][m]`: a two-dimensional array of integers representing the type of products on each shelf in each aisle Returns - `string`: either Possible or Impossible Input Format The first line contains an integer `q`, the number of queries. Each of the next `q` sets of lines is as follows: The first line contains an integer n, the number of aisles. The second line contains an integer m, the number of shelves in each aisle. Each of the next n lines contains m space-separated integers describing row `aisles[i]`. Constraints - 1leq qleq 10 - 1leq nleq 100 - 1leq mleq 100 - 0leq textit{aisles}[i][j]leq 100 Output Format For each query, print Possible on a new line if the aisles can be arranged as specified. Otherwise, print Impossible. Sample Input 0 2 2 3 1 2 0 0 1 2 2 2 0 1 2 2 Sample Output 0 Possible Impossible Explanation 0 We perform the following q=2 queries: 1. In the first query, we can rearrange the shelves in the first aisle to have products 2, 0, 1 and the second aisle already satisfies the condition. Thus, the output is Possible. 2. In the second query, it is not possible to rearrange the aisles to meet the condition as both aisles would contain more than one type of product on different shelves. Thus, the output is Impossible.
answer:def organizeAisles(aisles): n = len(aisles) m = len(aisles[0]) for aisle in aisles: unique_products = set(aisle) if len(unique_products) != m: return "Impossible" return "Possible"
question:Problem You have been given a 2D grid of characters and a target word. Your task is to find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are horizontally or vertically neighboring. The same letter cell may not be used more than once. # Task Implement the `wordExists()`/`word_exists()` function, which takes in two arguments: 1. `grid`: a 2D list of characters. 2. `word`: a string representing the target word. The function should return `True` if the word exists in the grid, and `False` otherwise. # Examples Example 1: ``` grid = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] word = "ABCCED" wordExists(grid, word) -> True ``` Example 2: ``` grid = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] word = "SEE" wordExists(grid, word) -> True ``` Example 3: ``` grid = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] word = "ABCB" wordExists(grid, word) -> False ``` # Constraints - The grid and the word contain only uppercase and lowercase English letters. - The grid has at most 200 rows and 200 columns. - The length of the word will be at most 10^3.
answer:def word_exists(grid, word): if not grid or not grid[0]: return False rows, cols = len(grid), len(grid[0]) def backtrack(r, c, index): if index == len(word): return True if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != word[index]: return False # mark the cell as visited temp, grid[r][c] = grid[r][c], '#' found = ( backtrack(r + 1, c, index + 1) or backtrack(r - 1, c, index + 1) or backtrack(r, c + 1, index + 1) or backtrack(r, c - 1, index + 1) ) grid[r][c] = temp # unmark the cell return found for row in range(rows): for col in range(cols): if backtrack(row, col, 0): return True return False
question:In a fantasy world, there are N magical orbs, each possessing a certain power level. These orbs need to be combined to achieve a total power level exactly equal to a certain target value T. A single combination involves choosing any one orb and removing it, resulting in a new collection of orbs. If an orb with power level X is removed, the power level target T gets reduced by X. The process can continue with the remaining collection of orbs and the updated value of T until no further combination is possible or the exact target T is reached. You are to determine whether it is possible to achieve the exact power level T using any sequence of combinations. Constraints: - 1 ≤ N ≤ 1000 - 1 ≤ Power level of each orb ≤ 1000 - 1 ≤ T ≤ 100000 Input: The input is given from Standard Input in the following format: N T power_1 power_2 ... power_N Output: Print "Yes" if it's possible to achieve the exact power level T, and "No" otherwise. Examples: Input: 5 9 2 3 7 8 10 Output: Yes Input: 4 5 1 2 3 4 Output: Yes Input: 3 11 2 4 6 Output: No
answer:def can_achieve_target(N, T, power_levels): dp = [False] * (T + 1) dp[0] = True for power in power_levels: for t in range(T, power - 1, -1): if dp[t - power]: dp[t] = True return "Yes" if dp[T] else "No" def main(): import sys input = sys.stdin.read data = input().split() N = int(data[0]) T = int(data[1]) power_levels = list(map(int, data[2:])) print(can_achieve_target(N, T, power_levels))