Appearance
question:Create a function that computes whether a given directed graph has any cycles. Your function should return `True` if there is at least one cycle in the graph, and `False` otherwise. Constraints * 1 ≤ |V| ≤ 10,000 * 0 ≤ |E| ≤ 100,000 Input |V| |E| u0 v0 u1 v1 : u|E|-1 v|E|-1 Here, |V| is the number of vertices, and |E| is the number of edges in the graph. The graph vertices are named with the numbers 0, 1, ..., |V|-1 respectively. ui and vi represent the source and target vertices of the i-th edge (directed). Output Print `True` if there is at least one cycle in the graph, and `False` otherwise. Examples Input 4 4 0 1 1 2 2 3 3 1 Output True Input 5 4 0 1 1 2 2 3 3 4 Output False
answer:def has_cycle(num_vertices, num_edges, edges): from collections import defaultdict # Build the graph graph = defaultdict(list) for u, v in edges: graph[u].append(v) # Helper function to perform DFS and detect cycle def dfs(vertex, visited, rec_stack): visited[vertex] = True rec_stack[vertex] = True for neighbour in graph[vertex]: if not visited[neighbour]: if dfs(neighbour, visited, rec_stack): return True elif rec_stack[neighbour]: return True rec_stack[vertex] = False return False visited = [False] * num_vertices rec_stack = [False] * num_vertices for node in range(num_vertices): if not visited[node]: if dfs(node, visited, rec_stack): return True return False
question:Michael is planning a treasure hunt for his friends. He designed a map with several waypoints, each labeled with a unique number. To add an extra level of challenge, Michael introduced a rule: Starting from the first waypoint, participants must find a path to the destination waypoint such that the sum of the waypoint numbers along the path is a prime number. They can move from one waypoint to another only if the sum of their numbers is within a specified range [A, B] and each waypoint can only be used once. Write a function to determine if such a path exists from the starting waypoint to the destination waypoint. INPUT The first line contains a single integer T, the number of test cases. Each test case consists of: - A line with four integers N (number of waypoints), A (lower bound of the range), B (upper bound of the range), and D (destination waypoint). - A line with N space-separated integers representing the waypoint numbers. OUTPUT For each test case, print "YES" if a valid path exists, "NO" otherwise. Constraints 1 ≤ T ≤ 10 1 ≤ N ≤ 100 1 ≤ A ≤ B ≤ 10,000 1 ≤ D ≤ N 1 ≤ Waypoint number ≤ 100 SAMPLE INPUT 2 4 10 50 4 11 15 29 4 5 15 70 5 20 25 30 35 40 SAMPLE OUTPUT YES NO Explanation [1] In the first test case, starting with waypoint 11, you can move to waypoint 29 (11 + 29 = 40, which is between 10 and 50 and is a prime number). From there, directly go to destination waypoint 4 (29 + 4 = 33, which is not a prime, but since the path from start to destination has total sum of 11 + 29 = 40 which is prime). Thus, the answer is YES. [2] In the second test case, no sequence of waypoints results in a path sum that is prime and within range [15, 70]. Hence, the answer is NO.
answer:def is_prime(n): Check if a number is prime. if n <= 1: return False if n <= 3: return True if n % 2 == 0 or n % 3 == 0: return False i = 5 while i * i <= n: if n % i == 0 or n % (i + 2) == 0: return False i += 6 return True def path_exists(N, A, B, D, waypoints): Check if there is a path to destination with the prime sum condition. from collections import deque def bfs(start): queue = deque([(start, waypoints[start], {start})]) while queue: current, path_sum, visited = queue.popleft() if current == D: if is_prime(path_sum): return True continue for i in range(N): if i != current and i not in visited: next_sum = path_sum + waypoints[i] if A <= next_sum <= B: queue.append((i, next_sum, visited | {i})) return False for start in range(N): if bfs(start): return "YES" return "NO" def treasure_hunt(t, tests): results = [] for test in tests: N, A, B, D = test[0] waypoints = test[1] results.append(path_exists(N, A, B, D-1, waypoints)) return results
question:Pulkit loves playing word games. He recently came across an interesting problem while reading a book of puzzles. Intrigued by the challenge, he decided to share it with his friend Ashish, who solved it quickly. Now it's your turn. Given a string s, you want to reorder the letters of the string such that no two adjacent characters are the same. If it's possible to reorder the string in such a way, return "Possible". Otherwise, return "Impossible". [Input] The first line contains an integer t denoting the number of test cases. Each of the next t lines contains a single string s which needs to be checked. [Output] For each test case, output "Possible" or "Impossible". [Constraints] 1 ≤ t ≤ 100 1 ≤ length of s ≤ 1000 s contains only lowercase English letters ('a' to 'z'). SAMPLE INPUT 3 aabb aaab abcdef SAMPLE OUTPUT Possible Impossible Possible
answer:from collections import Counter import heapq def is_possible_rearrange(s): Determines if it's possible to rearrange string s such that no two adjacent characters are the same. # Count the frequency of each character freq = Counter(s) # Max heap based on character frequency max_heap = [(-cnt, char) for char, cnt in freq.items()] heapq.heapify(max_heap) prev_count, prev_char = 0, '' result = [] while max_heap: count, char = heapq.heappop(max_heap) # Append current character to result result.append(char) # If there's a previously processed character, push it back to the heap if prev_count < 0: heapq.heappush(max_heap, (prev_count, prev_char)) # Decrease the count and set previous character to current prev_count, prev_char = count + 1, char # If the length of result is equal to the original string, it's possible if len(result) == len(s): return "Possible" else: return "Impossible" def process_test_cases(t, test_cases): Processes multiple test cases. results = [] for s in test_cases: results.append(is_possible_rearrange(s)) return results
question:You are given a string that consists of a mix of letters and digits. Your task is to reorder the string such that all letters appear in their original order, and all digits appear in their original order, but all digits must come before any letters. For example, given the input string "a1b2c3", the output should be "123abc". Function signature: `def reorder_string(s: str) -> str:` # Input - A single line containing the string `s` (1 ≤ |s| ≤ 1000), where |s| denotes the length of the string. The string consists of only alphanumeric characters. # Output - Print the reordered string. # Examples Example 1 **Input:** ``` a1b2c3 ``` **Output:** ``` 123abc ``` Example 2 **Input:** ``` abc123 ``` **Output:** ``` 123abc ``` Example 3 **Input:** ``` 1a2b3c ``` **Output:** ``` 123abc ``` # Note In the given examples, the order of letters and digits within their respective groups remains the same, but digits preceed letters in the output. To solve the problem, extract digits and letters separately from the input string, then concatenate the digits followed by the letters maintaining their original order.
answer:def reorder_string(s: str) -> str: digits = ''.join(filter(str.isdigit, s)) letters = ''.join(filter(str.isalpha, s)) return digits + letters